1.6. Максимальный поток через сеть.

Сетью называется ориентированный граф G=< V, U >, в котором выделены два множества полюсных вершин V⁺ и V^-, таких, что из каждой вершины

v_i⁺ V⁺ дуги только исходят, в каждую вершину v_i^- V^- дуги только входят и каждая вершина v_i V/ (V⁺ V^-) коинцидентна как входящим, так и исходящим дугам.

Каждой дуге сети сопоставляют положительное число, определяющее ее «пропускную способность».

Теорема 1.3. Максимальный поток Ф_max через сеть равен минимальной пропускной способности ее разреза.

Для определения Ф_max через заданную сеть G строят вспомогательный граф (граф достижимости) G_g = =< V_g, U_g >, каждая вершина которого взаимно однозначно соответствует дуге заданного графа G и две вершины соединены ребром тогда и только тогда, когда соответствующие им дуги входят в исходной сети G. Тогда пустой подграф графа G_g взаимно однозначно определяет разрез исходной сети G_. Минимальная сумма способностей дуг, вошедших в разрез, согласно т. 1.3. равна искомому максимальному потоку Ф_max.

Пример 12. Найти максимальный поток через сеть G (рис. 1.14). Пропускные способности дуг записаны около соответствующих дуг сети G.

n e d b

^{a; 5 n;7}

^{1 0 10 p}

^{b;2 m; 3}

^{p;2 a k c m}

^{c; 4 d; 3 k;4}

^{e; 2}

Рис. 1.14 Рис. 1.15

Построим граф достижимости G_g (рис. 1.15).

Используя алгоритм выделения пустых подграфов, выделим их в графе достижимости (рис. 1.16)

n e d b

^{a k c m}

^{n e d n e}

^{p p}

^{a k c a k}

^{n e n n}

^{p p p}

^{a k a a n}

ⁿ

^p

^{a n p Ø p Ø Ø}

^{p Е}₅ ^Е₇ ^Е₈

^{Ø Ø Ø Ø}

^Е₂ ^Е₃ ^Е₄ ^Е₆

^Ø

^Е₁

Рис. 1.16

Вычислим пропускную способность каждого разреза:

E₁ = {b,d,e,n, p} -2+3+2+7+2=16, E₅ = {b,c,a}-2+4+5=11,

E₂ = {b,d,e,a}-2+3+2+5=12, E₆ = {m,e,n,p}-3+2+7+2=14,

E₃ = {b,d,k,n}-2+3+4+7=16, E₇ = {m,e, a}-3+2+5=10,

E₄ = {b,c,n,p} -2+4+7+2=15, E₈ = {m,k,n}-3+4+7=14.

Разрез {m,e,a} с минимальной пропускной способностью, равной 10, определяет максимальной поток Ф_max=10 через сеть.■