Определение

ОПРЕДЕЛЕНИЕ

МАКСИМАЛЬНЫЕ ПОТОКИ

I 7(6) S

5 (8)

11 (7) 16 (7) 10 (8)

9 (8) 24 (1)

Рис. 6.4

Здесь ребрам сети приписаны значения их пропускных способностей, в скобках указаны значения потока по ребрам сети.

Величина потока, приведенного на рис. 6.4, равна 18.

В общем случае величина потока в сети задает суммарное количество ресурса, передаваемого по сети от истока к стоку.

Среди различных потоков, которые могут быть определены для заданной транспортной сети, особый интерес представляют такие потоки, величина которых является наибольшей.

Поток y транспортной сети N = (G, c) называется максимальным потоком, если y(N) = ,

где F - множество всех потоков в сети N.

Ребро u сети N = (G, c), для которой задан поток y, называется полностью нагруженным, если y(u) = c (u).

Поток y транспортной сети N = (G, c) называется полным потоком, если всякий путь в N, ведущий из I в S, содержит хотя бы одно полностью нагруженное ребро.

Упражнение.

1. Показать, что всякий максимальный поток является полным потоком.

2. Привести примеры транспортных сетей, имеющих единственный максимальный поток, несколько разных максимальных потоков. Может ли множество максимальных потоков транспортной сети быть бесконечным?

Напомним, что если W - путь в некотором графе, то E (W) обозначает множество ребер этого пути.

Для построения полного потока в произвольной транспортной сети N = (G, c), где G = (V, U), можно воспользоваться приводимым ниже методом насыщения дуг.

Дата добавления: 2015-03-31