Несколько источников и стоков

Предположим, что множество узлов сети разбито на три множества: S – множество источников, Т – множество стоков, R – множество промежуточных узлов. Расширим сеть, добавив два узла S^* и Т^* и все дуги (S^*, S) и (Т, Т^*). Доопределим значения пропускных способностей на вновь введенных дугах:

r^*(S^*, x_i) = ¥, x_i Î S;

r^*(x_j, T^*) = ¥, x_j Î T.

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

3.2. Решение задачи о максимальном потоке

в табличной форме

Метод расстановки пометок на графе имеет большую наглядность для уяснения алгоритма. Однако при практических расчетах, особенно при постановке задачи для расширения на ЦВМ, часто более удобным является решение задачи в табличной форме. Рассмотрим решение задачи для случая определения максимального потока в многоуровневом графе [5]. Решение приводится на основе использования многомерных матриц (пп. 1.4, 1.5). Условие задачи зададим с помощью многомерной матрицы

,

где - номера начального и конечного уровней; - номера начальной и конечной вершин графа; - пропускные способности дуг из вершины j⁺ (уровня ) в вершину (уровня ).

 

Общий шаг алгоритма. Общий шаг состоит из трех действий.

1. Помечаем столбец, соответствующий вершине-источнику , знаком *. Затем отыскиваем в строке все положительные . Содержащие их столбцы помечаем сверху числом, соответствующим номеру источника . Далее переходим к просмотру тех строк, которые имеют те же номера, что и отмеченные столбцы. В каждой строке отыскиваем все положительные , расположенные в непомеченных столбцах, и отмечаем эти столбцы номером просматриваемой строки . Процесс оканчивается: а) когда помечен сток; б) когда все строки просмотрены и нельзя отметить новые столбцы. В случае «а» новый путь из источника в сток находим, начиная от стока по отметкам столбцов. Последняя вершина пути – сток . По отметке, например над столбцом , находим предшествующую вершину . Число отметим знаком минус

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

В случае «б» алгоритм поиска нового пути закончен.

2. Определяем величину, на которую можно увеличить поток на найденном пути, e = min { }.

3. Вычисляем новые пропускные способности дуг. Для этого из всех вычитаем e, а ко всем прибавляем e. Получаем новую матрицу пропускных способностей. Затем стираем в таблице все пометки и возвращаемся к действию 1.

Для определения полученного максимального потока вычитаем из всех элементов первоначальной матрицы R(2,2) соответствующие элементы матрицы, полученной на последнем шаге. Положительные значения найденных разностей дают величины потоков по дугам многомерного графа.

Данное обобщение метода Форда-Фалкерсона на многомерный случай позволяет использовать алгоритм для решения многих задач, сводящихся к потоковым.