4.4. Пример

Рассмотрим неориентированный граф изображенный на рис. 11.9. Пропускные способности показаны цифрами, стоящими

Рис. 11.9. Граф из примера 4.4.

у ребер. Нужно найти максимальный поток между каждой парой вершин графа Применим вышеописанный алгоритм.

Шаг 1.

Шаг 2.

Шаг 3. Граф не может быть сконденсирован. Берем (произвольно) Вычисляя максимальный поток (от найдем, что минимальным разрезом будет а значение разреза равно 24.

Шаг 4. Дерево и пропускные способности его ребер изображены на рис. 11.10а.

Шаг (т. е. имеет теперь, как показана на рис. 11.10а, две вершины:

Шаг 2. Берем

Шаг 3. Выбираем (произвольно) Полученный затем сконденсированный граф изображен на рис. 11.106. Вычисляя для него максимальный поток, порождаем минимальный разрез где Значение этого разреза равно 23.

Шаг -вершина заменяется теперь двумя новыми -вершинами и ребром между ними со значением 23. Так как а то ребро удаляется и заменяется ребром где

Шаг (т. е. имеет теперь 3 вершины, как показано на рис. 11.10в).

Шаг 2. Возьмем

Шаг 3. Берем Сконденсированный граф изображен на рис. Минимальный разрез со значением 30 равен где

Шаг -вершина теперь заменяется двумя новыми -вершинами а новое дерево показано на рис. 11.10д.

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

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

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

вычислить непосредственно с помощью (11.10). Она имеет вид

Все 5 (в общем случае разрезов графа соответствующие ребрам дерева показаны пунктиром на рис. 11.11.

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

Рис. 11.11. Разрез, дающий дерево

Рис. 11.12. Другое потоково эквивалентное дерево.

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