4. Сетевые модели

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

Введем граф приращения следующим образом:

Вершины в графе те же, что и в сети, а дуг в два раза больше, причем соответствуют нормальная дуга и обращенная дуга , длины которых, определены правилом:

Поток будет максимальным, если в нет путей из в нулевой длины.

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

  1. Задание начального допустимого потока .

  2. .

  3. Построение графа приращений .

  4. Определение кратчайшего расстояния в и соответствующей ему цепи кратчайшего пути.

  5. Если , то выполнение п.6, иначе выполнение п.10.

  6. Строим простой поток по цепи .

  7. (в общем случае: ).

  8. .

  9. Переходим к пункту 3.

  10. Окончание алгоритма.

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

Если нам известен некий допустимый поток в сети , то берем его в качестве начального и используем предыдущий алгоритм.

Рассмотрим вопрос нахождения начального допустимого потока:

Для нахождения начального потока строим вспомогательную сеть : , в которой множество вершин включает, кроме , еще 2 дополнитльные вершины и , а множество дуг определяется следующим образом: каждой дуге будет соответствовать 3 дуги:

, ,

Кроме того добавляем дугу

Пропускные способности определяются следующим образом:

, где - очень большое целое число.

Тогда сеть - транспортная.

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

Теорема. Если насыщенный поток из , то поток в сети является допустимым из в , а его величина равняется .

Если - максимальный, но ненасыщенный в сети , то в нет допустимых потоков вообще.