Утверждение 5.

1. Вектор u' с компонентами, определенными формулой (9), является потоком в сети S;

2. Р (u') = Р (u) + D, (10)

где через Р (u) обозначена величина потока u (см. конец раздела 1 перед примером 2) ■

Таким образом, по любому потоку u, не являющемуся максимальным, можно построить поток u' с бóльшей величиной Р (u'). Именно это построение (состоящее из рассмотренных вы-ше четырёх этапов) и лежит в основе АФФ.

Для завершения описания алгоритма нам понадобится почти очевидное

Утверждение 6. Нулевой вектор u = (0, 0,..., 0) является потоком в сети ■

Алгоритм Форда-Фалкерсона (АФФ)

1. Положить u = (0, 0,..., 0).

2. Выполнить алгоритм расстановки меток по потоку u. При выходе из этого алгоритма на шаге 7 АФФ завершает работу; поток u является максимальным. При выходе из этого алгоритма на шаге 3 перейти на следующий шаг 3 АФФ.

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

4. Вычислить инкремент D найденного увеличивающего пути, исходя из потока u.

5. Построить новый поток u' по формуле (9), исходя из потока u, пути p и декремента D.

6. Положить u = u' и вернуться на шаг 2 ■

Утверждение 7. При целочисленных пропускных способностях с_j (j = 1, 2,..., m) все пото-ки, построенные АФФ, будут целочисленными, и процесс построения потоков оборвётся за ко-нечное число шагов ■

Это достаточно простое утверждение не означает, что при нецелочисленных пропускных способностях АФФ обязательно будет «циклиться». Более того, при разумном (а не произволь-ном) выборе вершины из множества помеченных и не просмотренных вершин на шаге 1 алго-ритма расстановки меток можно не только гарантировать конечность АФФ при любых пропус-кных способностях, но и дать полиномиальную оценку числа необходимых операций.

Пример 11. Используя АФФ, найти максимальный поток в сети, показанной на рис.10.

\

Рис.10

В соответствии с АФФ начнём с нулевого потока.

1. Положим u = (0, 0, 0, 0, 0).

2. Найдём метки, как это делалось в примере 7. Определим исходную таблицу, являющу-юся инициализацией для расстановки меток:

Таблица 3. Инициализация основной таблицы

и просто выпишем результаты последовательных итераций:

Таблица 3.1. Итерация 1

Таблица 3.2. Итерация 2

Поскольку сток (вершина 4) помечен, метки построены. Они приведены в последней строке таблицы 3.2.

3. Построим увеличивающий путь (см. алгоритм 2). Он таков: 1→2→4.

4. Найдём инкремент (см. алгоритм 3). Положим D = 8; тогда D ₁ = 8, D ₂ = 6.

5. Найдём новый поток (см. алгоритм 4). Положим u' = (6, 0, 0, 6, 0) и перейдём на шаг 2.

2. Найдём метки, как это делалось в примере 7. Определим исходную таблицу, являющу-юся инициализацией для расстановки меток:

Таблица 4. Инициализация основной таблицы

и просто выпишем результаты последовательных итераций:

Таблица 4.1. Итерация 1

Таблица 4.2. Итерация 2

Заметим, что исходя из вершины 2, мы не пометили новые вершины. Вершину 4 нельзя поме-тить, поскольку поток в дуге (2, 4) равен ограничению, а вершину 3 нельзя пометить, потому что она уже была помечена. Единственное изменение на 2-ой итерации состоит в том, что вершина 2 перешла в состояние 3 из состояния 2.

Таблица 4.3. Итерация 3

Поскольку сток оказался помеченным, то метки построены. Они приведены в последней строке таблицы 4.3.

3. Построим увеличивающий путь (см. алгоритм 2). Он таков: 1→3→4.

4. Найдём инкремент (см. алгоритм 3). Положим D = 5; тогда D ₁ = 5, D ₂ = 4.

5. Найдём новый поток (см. алгоритм 4). Положим u' = (6, 4, 0, 6, 4) и перейдём на шаг 2.

2. Найдём метки, как это делалось в примере 7. Определим исходную таблицу, являющу-юся инициализацией для расстановки меток:

Таблица 5. Инициализация основной таблицы

и просто выпишем результаты последовательных итераций:

Таблица 5.1. Итерация 1

Таблица 5.2. Итерация 2

Таблица 5.3. Итерация 3

Оказалось невозможным пометить вершину 4 (сток), поскольку обе дуги: (2, 4) и (3, 4) на-сыщены в прямом направлении (в них поток равен ограничению). Нет ни одной вершины в со-стоянии 2. В соответствии с АФФ это означает, что поток u = (6, 4, 0, 6, 4), найденный перед по-следними итерациями, является максимальным потоком, т.е. потоком, величина которого Р (u) максимальна. Так как сумма потоков в дугах, выходящих из источника, равна 10, то величина максимального потока Р (u) = 10 ■

Задание 6. Используя АФФ, найти максимальные потоки в сетях, показанных на рисунке. Для образца см. пример 11.

01	02
03	04
05	06
07	08
09	10
11	12
13	14
15	16

■

Задание 7. Используя АФФ, найти максимальный поток в сети с графом, показанным на рис.1, и со следующими пропускными способностями:

1) (12,7,3,1,2,11,14,13,5,6,12,7).

2) (3,4,18,4,5,19,3,4,8,2,7,3).

3) (1,9,4,27,8,33,5,25,3,2,5,20).

4) (9,6,4,28,3,2,31,4,22,5,2,7,).

5) (24,5,8,9,29,3,2,6,33,41,2,21).

6) (9,28,27,10,8,9,6,19,8,3,7,24).

7) (5,8,7,8,5,2,11,2,3,8,18,9).

8) (10,3,2,29,35,41,8,5,27,10,7,9).

9) (44,15,8,3,32,39,8,7,25,29,3,12).

10) (22,5,28,19,4,6,8,1,19,7,4,4).

11) (5,8,1,4,15,33,4,22,5,30,1,2).

12) (11,14,13,5,8,18,9,10,3,27,10,8).

13) (9,6,19,8,3,2,31,33,4,22,5,5).

14) (4,6,8,1,19,7,4,8,7,3,12,22) ■

Дата добавления: 2015-10-16