4.3. Алгоритм построения максимального потока между всеми парами вершин

Алгоритм, описанный в настоящем разделе, порождает дерево которое потоково эквивалентно неориентированному графу Максимальный поток между двумя вершинами

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

графа может быть следующим образом найден по этому дереву:

где единственная цепь, проходящая по ребрам дерева и ведущая от Каждая вершина из соответствует вершине из является пропускной способностью ребра из

Идея алгоритма проста: так как существует дерево потоково эквивалентное графу и так как содержит только ребер, то все, что необходимо, — это вычислить пропускные способности ребер дерева Описанный в данном разделе алгоритм вычисляет пропускные способности ребер дерева этапов. Каждый этап состоит в вычислении потока в графе, получаемом последовательно из ранее построенного графа с помощью конденсации, как об этом говорилось выше в разд. 4.2.

4.3.1. Описание алгоритма.

Так как алгоритм порождает дерево постепенно и так как на любом из этапов действия алгоритма «вершины» из могут быть на самом деле множествами вершин из то мы будем, во избежание недоразумений, называть вершины из -вершинами, а вершины из -вершинами. Ниже дается достаточно комментариев, чтобы сделать алгоритм понятным.

Шаг 1. Положить

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

Шаг 2. Найти множество содержащее более чем одну -вершину. Если такого не существует, то перейти к шагу 6, в противном случае — к шагу 3.

Шаг 3. Если бы было удалено из то дерево распалось бы на некоторое число поддеревьев (связанных компонент). Сконденсировать -вершины в каждом поддереве в одну вершину и образовать сконденсированный граф. Взять любые две вершины и найти минимальный разрез отделяющий от с помощью вычисления максимального потока (от

Шаг 4. Удалить из -вершину вместе с ребрами, ей инцидентными, и заменить ее на две -вершины, составленные из -вершин множеств и на ребро между ними с пропускной способностью Итак, для всех -вершин которые до замены были инцидентны (скажем, с пропускной способностью ребра добавить к ребро если или же к добавить ребро

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

Замечание. Как уже было отмечено в разд. 4.2, Гомори и Ху [14] показали, что лежит целиком или в или в так что возможны только два указанных выше случая.

Шаг 5. Положить Вершины из являются теперь множествами -вершин где заменена двумя -вершинами как объяснялось выше. Перейти к шагу 2.

Шаг 6. Останов. будет теперь требуемым потоково эквивалентным графу деревом, и его -вершины являются теперь единственными -вершинами. Пропускные способности ребер из соответствуют значениям независимых разрезов в графе Равенство (11.10) можно теперь использовать для вычисления (для любых непосредственно из

То обстоятельство, что вышеприведенный алгоритм дает оптимальный результат, следует непосредственно из свойств минимальных разрезов и свойств потоково эквивалентного графу дерева, приведенных выше в разд. 4.1 и 4.2. Формальное доказательство можно найти в книге Ху [16].