Лабораторная работа 14. Задача о максимальном потоке в сети

Рассмотрим пример. На графе G, приведенном на рис.6.1. найти максимальный поток, который может быть пропущен из вершины 1 в вершину 9 и разрез с минимальной пропускной способностью, в качестве пропускных способностей d(v) возьмем значения из таблицы 1.

2 8

 

 

 

1 4 7

 

 

5

 

3 6 9

Рис.6.1.

Таблица 1

 

d12

d14

d13

d28

d27

d24

d34

d35

d36

d47

d45

d57

d56

d59

d69

d78

d79

d89

Решение.

Потоки по всем дугам полагаем равными нулю, т.е.

X₁₂=0; X₁₄=0; X₁₃=0; X₂₈=0; X₂₇=0; X₂₄=0;

X₃₄=0; X₃₅=0; X₃₆=0; X₄₇=0, X₄₅=0; X₅₇=0;

X₅₉=0; X₅₆=0; X₆₉=0; X₇₈=0; X₇₉=0; X₈₉=0;

 

Отыскание увеличивающего пути.

 

Помечаем вершину 1 пометками q(1)=1000, v(1)= -. Все остальные вершины не помечены, для них q(i)=0, v(i)= -.

Номер вершины i q(i) v(i)

1: 1000 -

 

Из вершины 1 помечаем вершины 2, 3, 4. Покажем как это делается на примере вершины 2. Поток, поступивший в вершину 1 равен 1000, по дуге (1, 2) d₁₂=1, X₁₂=0, поэтому дополнительный поток, который может поступить в вершину 2 q(2)=min(q(1), d₁₂- X₁₂)=min(1000, 1-0)=1. Вершина 2 помечается по прямой дуге (1, 2), поэтому v(i)=(1, 2). После аналогичной пометки вершин 3, 4 получаем

Номер вершины i q(i) v(i)

1: 1000 -

2: 1 (1, 2)

3: 1 (1, 3)

4: 2 (1, 4)

 

Затемнена просмотренная вершина, все остальные вершины не просмотрены.

Из вершины 2 помечаем вершины 7 и 8

 

Номер вершины i q(i) v(i)

1: 1000 -

2: 1 (1, 2)

3: 1 (1, 3)

4: 2 (1, 4)

7: 2 (4, 7)

8: 1 (2, 8)

Далее из вершины 3 помечаем 5 и 6

 

 

Номер вершины i q(i) v(i)

1: 1000 -

2: 1 (1, 2)

3: 1 (1, 3)

4: 2 (1, 4)

7: 2 (4, 7)

8: 1 (2, 8)

5: 1 (3, 5)

6: 1 (3, 6)

 

Аналогично вершина 4.

После просмотра вершины 7 становится помеченной вершина 9

 

 

Номер вершины i q(i) v(i)

1: 1000 -

2: 1 (1, 2)

3: 1 (1, 3)

4: 2 (1, 4)

7: 2 (4, 7)

8: 1 (2, 8)

5: 1 (3, 5)

6: 1 (3, 6)

9: 2 (7, 9)

 

Эта вершина является стоком, в нее пришел дополнительный поток q(9)=2. Восстанавливаем путь по которому пришел этот поток, используя значения v(i). Этот путь выглядит следующим образом

1, (1, 4), 4, (4, 7), 7, (7, 9), 9

По дугам этого пути увеличиваем потоки на величину q(9)=2. В результате получаем

 

X₁₂=0; X₁₄=2; X₁₃=0; X₂₈=0; X₂₇=0; X₂₄=0;

X₃₄=0; X₃₅=0; X₃₆=0; X₄₇=2, X₄₅=0; X₅₇=0;

X₅₉=0; X₅₆=0; X₆₉=0; X₇₈=0; X₇₉=2; X₈₉=0;

 

После аналогичного отыскания увеличивающих путей дважды получим

 

X₁₂=1; X₁₄=2; X₁₃=1; X₂₈=0; X₂₇=0; X₂₄=1;

X₃₄=1; X₃₅=0; X₃₆=0; X₄₇=3, X₄₅=1; X₅₇=0;

X₅₉=0; X₅₆=1; X₆₉=1; X₇₈=0; X₇₉=3; X₈₉=0;

 

Начинаем заново поиск увеличивающего пути из вершины t.

Помечаем вершину 1 пометками q(1)=1000, v(1)= -. Все остальные вершины не помечены, для них q(i)=0, v(i)= -.

 

Из вершины 1 невозможно пометить по выходящим из нее дугам ни одной вершины

Номер вершины i q(i) v(i)

1: 1000 -

 

Все помеченные вершины просмотрены, поэтому максимальный поток найден.

Его величина равна Q=X₆₉+X₇₉+X₈₉=4. Разрез с минимальной пропускной способностью V(E1, E2)={(1, 2), (1, 3), (1, 4)} изображен на рис.1 двойной линией, Е1={1}, E2={2, 3, 4, 5, 6, 7, 8, 9}.