2.2. Пример

Рассмотрим граф, изображенный на рис. 11.1, и возьмем в качестве источника вершину а в качестве стока — вершину Пропускные способности дуг указаны на рисунке. Требуется найти максимальный поток от

В качестве начального возьмем поток с нулевыми значениями на всех дугах. Алгоритм работает следующим образом.

Шаг 1. Припишем вершине пометку

Шаг 2. (I) Множество вершин не помечена) есть

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

вершине приписывается , т. е.

(II) Множество вершин не помечена) является пустым. Итак, помечена и просмотрена, и помечены и не просмотрены, а все остальные вершины не помечены. Повторяем шаг 2 и первой просматриваем вершину Множество не помечена) есть

для пометкой будет

Рис. 11.1. Граф из примера 2.2

(II) Множество не помечена) является пустым. Теперь вершины помечены и просмотрены, и помечены, но не просмотрены.

Беря для просмотра и повторяя шаг 2, придем к следующим пометкам:

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

Переходя к шагам 4 и 5, получим:

Вид потока в конце шага 5 и пометки вершин до их стирания на шаге 6 показаны на рис. 11.2а. Все потоки показаны подчеркиванием.

Стирая пометки у вершин и возвращаясь к шагу 1 для второго прохода, получим следующие новые пометки вершин (помеченные, но не просмотренные вершины просматриваются в порядке возрастания их номеров).

Шаг. 3.

Пометкой для будет

пометкой для будет

пометкой для будет ;

теперь вершина помечена и просмотрена.

Пометкой для будет теперь вершина помечена и просмотрена.

Пометкой для будет пометкой для будет ;

теперь вершина помечена и просмотрена,

вершина также помечена и просмотрена.

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

Пометка для будет теперь вершина помечена и просмотрена.

Пометкой для будет теперь вершина помечена и просмотрена.

Пометкой для будет

Шаги 4 и 5.

Новые потоки увеличились следующим образом:

все остальные значения потока не изменились.

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

Продолжая дальше, получаем после каждого прохода алгоритма потоки и пометки, изображенные последовательно на рисунках Алгоритм заканчивает работу, когда вершина не может быть помечена; «заключительные» пометки показаны на рис. 11.2е.

Поток на рис. 11.2е является поэтому максимальным потоком со значением 29, а соответствующий минимальный разрез показан пунктиром на рис.