Алгоритм поиска увеличивающего пути

1. Определить состав множеств N, I, R. Дуги множества N из дальнейшего рассмотрения исключить. Окрасить вершину s.

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

Правила окрашивания вершины y и дуги (x, y) при уже окрашенной вершине x состоят в следующем:

а) если дуга (х, у) принадлежит I, то окрашивается вершина у и дуга (х, у);

б) если дуга (у, х) принадлежит R, то окрашивается вершина у и дуга (у, х);

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

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

Пример: определить увеличивающий путь в графе, изображённом на рисунке

Рядом с дугами графа указаны буквы I, R, N, устанавливающие принадлежность дуг к соответствующим множествам.

Рис. 62

1. Окрашивается вершина s. Она связана с вершинами а и с, но продолжить путь мы можем только по дуге (s, a), так как , а .

2. Окрашивается вершина a, дуга (s, a). Вершина a связана с вершинами s, b, с, d. Так как вершина s уже окрашена, а , то продолжить путь мы можем только через вершину c.

3. Окрашивается вершина c, дуга (a, c). Вершина c связана с вершинами s, a, b, d. Так как вершины s, а окрашены, а , то продолжить путь мы можем через вершину b и вершину d.

4. Окрашивается вершина b и дуга (b, c), вершина d и дуга (c, d). Осталась только одна неокрашенная вершина t, и . Значит, перейти в вершину t мы можем только через вершину b.

5. Окрашивается вершина t, дуга (b, t).

Возвращаемся из вершины t в вершину s по окрашенным дугам (b, t), (b, c), (a, c), (s, a).

В итоге получаем увеличивающий путь: (s, a), (a, c), (b, c), (b, t).

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

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

Задача о максимальном потоке состоит в поиске способов пересылки максимального количества единиц потока из источника в сток при условии отсутствия превышения пропускных способностей дуг исходного графа.

Будем через обозначать количество единиц потока, прошедших по дуге .

При любом потоке из вершины s в вершину t количество единиц, выходящих из любой вершины x должно быть равно количеству единиц, входящих в эту вершину, то есть (1) , где ― множество вершин y , для которых в исходном графе существует дуга , а ― множество вершин y, для которых в исходном графе существует дуга . Кроме того, количество единиц потока, проходящих по каждой дуге , не должно превышать пропускной способности этой дуги: (2), где A - это множество дуг графа.

Суммарное число единиц потока, выходящих из источника, должно быть равно суммарному числу единиц потока, входящих в сток. Если указанное число обозначить через , то это условие можно представить так:

(3)

(4)

Любой поток из вершины s в вершину t должен удовлетворять условиям (1-4).

Задача о максимальном потоке может быть сформулирована так: «Найти поток, который удовлетворяет условиям (1-4) и максимизирует величину ». Для решения этой задачи Фордом и Фалкерсоном был предложен следующий алгоритм.