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

Сетью называется ориентированный граф 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}

^{10 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 через сеть.■

Задачи для самостоятельного решения.

1. Определить вершинное число независимости и число вершинного покрытия графа G = < V, U >, у котрого V = {1,2,3,4,5,6,7},

U= {(1,2),(1,6),(1,7),(2,3),(3,4), (3,7), (4,5), (4,7), (5,6), (6,7)}. Показать

множество вершин графа G, соответствующих найденному числу

вершинного покрытия.

2. Определить реберное число независимости и число реберного

покрытия графа G, заданного в задаче 1. Показать множество ребер графа G, соответствующих найденному числу реберного покрытия.

3. Определить вершинное число внешней устойчивости графа G = <V,U>,

у которого V = {1,2,3,4,5,6}, U= {(1,2),(1,6),(2,3), (2,5), (2,6), (3,4),

(3,5), (4,5), (5,6) }.

4. Определить реберное число внешней устойчивости графа G, заданного

в задаче 3.

5. Определить положительное и отрицательное вершинное число

внешней устойчивости ориентированного графа G = < V, U >, у

котрого V = {1,2,3,4,5,6}, U= {(1,2),(1,6),(2,6),(3,5), (4,3), (5,2), (5,4),

(6,5)}.

6. Определить плотность графа G = < V, U >, у котрого V =

={1,2,3,4,5,6,7}, U= {(1,2),(1,7),(2,3),(2,4), (2,5), (2,7), (3,4),(4,5), (4,7),

(5,6), (5,7),(6,7)}.

7. Найти максимальный поток через сеть G, если известна пропускная

способность дуг:

a = (v_1, v₂)-3, b= (v_1, v₃)-2, c = (v_1, v₄)-4, d= (v_3, v₄)-2,

e = (v_2, v₅)-3, f = (v_2, v₇)-5, g = (v_4, v₆)-4, h = (v_4, v₇)-1,

k = (v_5, v₈)-5, m = (v_6, v₈)-3, n = (v_6, v₉)-2, p = (v_7, v₉)-5,

r = (v_5, v₁₀)-6, s = (v_8, v₁₀)-4, t = (v_9, v₁₀)-2.