Поиск максимального потока

Задача о максимальном потоке состоит в поиске способа пересылки максимального количества единиц потока из источника в сток.

Алгоритм 6. Алгоритм поиска максимального потока.

Шаг 1. Выбрать любой начальный поток в графе G =(V, E) из источника s в сток t, то есть выбрать любой набор величин f (x, y), удовлетворяющий соотношениям 7.1-7.4.

Шаг 2. Применить к графу G =(V, E) алгоритм поиска увеличивающей цепи (алгоритм 5).

Шаг 3. Если увеличивающая цепь найдена, то увеличить поток вдоль найденной цепи по правилам, приводимым в разд. 7.2, и вернуться к шагу 2. В противном случае закончить алгоритм поиска максимального потока. Максимальный поток найден.

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

Для графа, изображенного на рис.7.1, максимальный поток будет найден за одну итерацию, на которой будет построена увеличивающая цепь, представленная на рис. 7.2, и увеличен поток вдоль найденной цепи на две единицы (рис. 7.3). Дальнейшее увеличение потока невозможно, так как в графе, изображенном на рис. 7.3, увеличивающая цепь не существует.