Алгоритм нахождения максимального потока

Задача. Задан орграф с пропускными способностями с, значения которых указаны рядом с каждой дугой. Найти максимальный поток из источника s в сток t.

Рисунок 3.1 - Исходный орграф

Решение. Пропустим по орграфу произвольный поток, для чего зададим для каждой дуги e потоковую функцию f, удовлетворяющую условиям:

1) ;

2) для каждой вершины, отличной от s и t, сумма потоковых функций входящих дуг равна сумме потоковых функций исходящих дуг.

Получим граф, изображенный на рис. 3.2, где первое число рядом с дугой обозначает ее пропускную способность, второе – потоковую функцию. Суммарный поток, исходящий из источника, Равный ему поток входит в сток:

Рисунок 3.2 - Орграф с суммарным потоком 9

Присвоим тип I каждой дуге, для которой потоковая функция меньше ее пропускной способности, и тип D- каждой дуге, для которой потоковая функция отлична от нуля.

Рисунок 3.3 - Орграф с указанными типами дуг

На рис 3.3 изображен граф с указанными типами дуг. Отметим, что дуга (s,a) является одновременно как дугой типа I, так и дугой типа D.

Попытаемся найти в графе увеличивающую цепь, т.е. простую цепь из источника в сток, в которой каждая дуга, направленная из s в t, (прямая дуга) имеет тип I, акаждая дуга, направленная из t в s, (обратная дуга) -тип D. Для этого будем помечать вершины и дуги графа, начиная с источника s и используя следующее правило:

- если вершина x помечена, дуга (x,y) не помечена и имеет тип I, вершина y не помечена, то помечается дуга (x,y) и ее конец y;

- если вершина x помечена, дуга (y,x) не помечена и имеет тип D, вершина y не помечена, то помечается дуга (y,x) и ее начало y;

- других случаев пометки вершин и дуг не существует.

Если в результате окажется возможным пометить сток t, то в графе существует увеличивающая цепь, по которой можно пропустить дополнительный поток, иначе такой цепи не существует, и текущий поток является максимально возможным.

Пометим прежде всего вершину s. Из двух дуг, исходящих из этой вершины, можно пометить только дугу (s,a), имеющую тип I, и ее конец a. Далее можно пометить дугу (a,c) и ее конец c. Нельзя пометить прямую дугу (a,b), имеющую тип D, и обратную дугу (d,a), т.к. она имеет тип I. Непомеченными остаются также их вершины b и d. Далее, исходя из вершины c, помечается обратная дуга (b,c) типа D и ее начало b. Дуга (c,d) и ее вершина d не помечаются, т.к. эта прямая дуга имеет тип D. Наконец, помечаются прямая дуга (b,t) типа I и ее конец-источник t.

Таким образом, найдена увеличивающая цепь (s,a), (a,c), (b,c), (b,t).

Найдем для увеличивающей цепи резерв увеличения потока по каждой прямой дуге : d(s,a)= 4,

Рисунок 3.4 - Орграф с увеличенным потоком

d(b,t)= 3; далее найдем резерв уменьшения потока по каждой обратной дуге : d(b,c)= 1. Минимальная из этих величин есть дополнительный поток, который можно пропустить по увеличивающей цепи. Новые значения потоковой функции в прямых дугах цепи , а в обратных дугах . Граф с увеличенным потоком изображен на рис. 3.4.

Можно видеть, что суммарный поток в этом графе равен 10. Вновь определим типы дуг (рис. 3.5).

Анализ этого графа показывает, что в нем можно пометить только дуги (s,a), (a,c) и их вершины a,c. Дальнейшие пометки невозможны, и сток t остается непомеченным. Следовательно, новых увеличивающих цепей построить нельзя, и найденный поток, равный 10, является максимальным.

Рисунок 3.5 - Орграф с новыми типами дуг

Варианты заданий

Определить максимальный поток из вершины s в вершину t для графа, изображенного на рис. 3.6, с пропускными способностями дуг с.

Рисунок 3.6 – Заданный орграф

1. c(e₁)=15; c(e₂)=4; c(e₃)=12; c(e₄)=10; c(e₅)=5; c(e₆)=3; c(e₇)=7; c(e₈)=10

2. c(e₁)=30; c(e₂)=8; c(e₃)=12; c(e₄)=20; c(e₅)=10; c(e₆)=8; c(e₇)=14; c(e₈)=20

3. c(e₁)=20; c(e₂)=6; c(e₃)=8; c(e₄)=15; c(e₅)=7; c(e₆)=4; c(e₇)=11; c(e₈)=15

4. c(e₁)=21; c(e₂)=7; c(e₃)=9; c(e₄)=16; c(e₅)=9; c(e₆)=6; c(e₇)=13; c(e₈)=17

5. c(e₁)=22; c(e₂)=8; c(e₃)=10; c(e₄)=17; c(e₅)=10; c(e₆)=7; c(e₇)=14; c(e₈)=18

6. c(e₁)=18; c(e₂)=10; c(e₃)=8; c(e₄)=15; c(e₅)=13; c(e₆)=2; c(e₇)=16; c(e₈)=15

7. c(e₁)=12; c(e₂)=3; c(e₃)=12; c(e₄)=13; c(e₅)=14; c(e₆)=8; c(e₇)=7; c(e₈)=19

8. c(e₁)=51; c(e₂)=10; c(e₃)=15; c(e₄)=4; c(e₅)=13; c(e₆)=10; c(e₇)=6; c(e₈)=21

9. c(e₁)=50; c(e₂)=9; c(e₃)=16; c(e₄)=5; c(e₅)=14; c(e₆)=9; c(e₇)=7; c(e₈)=22

10. c(e₁)=15; c(e₂)=4; c(e₃)=12; c(e₄)=10; c(e₅)=5; c(e₆)=3; c(e₇)=7; c(e₈)=10

11. c(e₁)=22; c(e₂)=12; c(e₃)=4; c(e₄)=11; c(e₅)=22; c(e₆)=5; c(e₇)=9; c(e₈)=14

12. c(e₁)=7; c(e₂)=21; c(e₃)=6; c(e₄)=13; c(e₅)=16; c(e₆)=23; c(e₇)=32; c(e₈)=8

13. c(e₁)=9; c(e₂)=31; c(e₃)=16; c(e₄)=6; c(e₅)=11; c(e₆)=14; c(e₇)=7; c(e₈)=11

14. c(e₁)=3; c(e₂)=21; c(e₃)=12; c(e₄)=20; c(e₅)=33; c(e₆)=11; c(e₇)=7; c(e₈)=15

15. c(e₁)=2; c(e₂)=41; c(e₃)=22; c(e₄)=11; c(e₅)=7; c(e₆)=4; c(e₇)=20; c(e₈)=15

16. c(e₁)=13; c(e₂)=7; c(e₃)=14; c(e₄)=11; c(e₅)=31; c(e₆)=15; c(e₇)=8; c(e₈)=3

17. c(e₁)=1; c(e₂)=6; c(e₃)=17; c(e₄)=18; c(e₅)=5; c(e₆)=22; c(e₇)=31; c(e₈)=12

18. c(e₁)=10; c(e₂)=41; c(e₃)=23; c(e₄)=7; c(e₅)=8; c(e₆)=9; c(e₇)=11; c(e₈)=14

19. c(e₁)=1; c(e₂)=5; c(e₃)=13; c(e₄)=17; c(e₅)=24; c(e₆)=19; c(e₇)=7; c(e₈)=17

20. c(e₁)=15; c(e₂)=3; c(e₃)=2; c(e₄)=1; c(e₅)=13; c(e₆)=8; c(e₇)=22; c(e₈)=15

21. c(e₁)=10; c(e₂)=7; c(e₃)=12; c(e₄)=10; c(e₅)=3; c(e₆)=4; c(e₇)=17; c(e₈)=10

22. c(e₁)=8; c(e₂)=16; c(e₃)=7; c(e₄)=8; c(e₅)=5; c(e₆)=2; c(e₇)=3; c(e₈)=12

23. c(e₁)=12; c(e₂)=4; c(e₃)=8; c(e₄)=11; c(e₅)=3; c(e₆)=4; c(e₇)=7; c(e₈)=15

24. c(e₁)=6; c(e₂)=8; c(e₃)=12; c(e₄)=14; c(e₅)=7; c(e₆)=5; c(e₇)=17; c(e₈)=15

25. c(e₁)=9; c(e₂)=6; c(e₃)=3; c(e₄)=11; c(e₅)=7; c(e₆)=2; c(e₇)=20; c(e₈)=7