Найдем максимальный поток в сети, показанной на рис. 8.2. с примером решения

Пример №30.

Найдем максимальный поток в сети, показанной на рис. 8.2. Для уменьшения количества итераций начнем с ненулевого допустимого потока (рис. 8.5).

Шаг 1. Метим источник меткой Найдем максимальный поток в сети, показанной на рис. 8.2. . Шаг 2. Из вершины можно пометить вершину меткой и вершину меткой . Из вершины помечается вершина меткой . Из вершины Найдем максимальный поток в сети, показанной на рис. 8.2. метится вершина меткой (рис. 8.6).

Шаг 3. Найдена увеличивающая цепь. Вершина Найдем максимальный поток в сети, показанной на рис. 8.2. помечена от вершины , вершина — от вершины , а вершина — от вершины . Причем все вершины помечены по прямым дугам.

Шаг 4. Увеличивающая цепь имеет вид Найдем максимальный поток в сети, показанной на рис. 8.2. . На каждой дуге увеличивающей цепи величина потока возрастает на 1 (рис. 8.7).

Шаг 5. Стираем все пометки и возвращаемся к шагу 1 (рис. 8.8).

Шаг 2. От вершины Найдем максимальный поток в сети, показанной на рис. 8.2. можно пометить вершину меткой . От вершины по обратной дуге можно пометить вершину меткой . От вершины по прямой дуге метится вершина Найдем максимальный поток в сети, показанной на рис. 8.2. меткой , а от вершины метится сток — меткой (рис. 8.8).

Шаг 3. Вершина Найдем максимальный поток в сети, показанной на рис. 8.2. получила пометку, следовательно, поток в сети можно увеличить.

Шаг 4. Увеличивающая цепь имеет вид

По ней можно увеличить поток на 1 (рис. 8.9).

Шаг 5. Стираем все пометки и возвращаемся к шагу 1 (рис. 8.10).

Шаг 2. Все дуги, выходящие из источника, насыщены. Ни одной из вершин нельзя приписать метку. Следовательно, найден максимальный поток. Множество Найдем максимальный поток в сети, показанной на рис. 8.2. помеченных вершин содержит единственную вершину . Тогда