7.2. Путь с наибольшей пропускной способностью

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

Теорема 1. Пропускная способность пути с наибольшей пропускной способностью от равна

где К — любой -разрез (в множестве дуг).

Доказательство. Пусть пропускная способность пути с наибольшей пропускной способностью. Так как каждый путь от должен содержать по крайней мере одну дугу из каждого -разреза, то для каждого разреза К будет выполняться неравенство

Поскольку в каждом должна присутствовать по крайней мере одна дуга с пропускной способностью, не превосходящей и поскольку, взяв по одной такой дуге из каждого -пути, мы получаем некоторый (по определению), то существует хотя бы один разрез, скажем К, для которого

Таким образом, разрез К, доставляющий минимум выражению

должен одновременно удовлетворять неравенствам (8.12) и (8.13), т. е. для него должно выполняться равенство. Отсюда следует справедливость теоремы.

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

Шаг 1. Начать с -разреза и найти наибольшую пропускную способность дуг из К.

Шаг 2. Построить остовный подграф где

Шаг 3. Найти множество вершин, достижимых из в графе А. (Построение множества описано в гл. 2.)

Шаг 4. Если то и любой -путь в остовном подграфе будет иметь наибольшую пропускную способность, равную Если перейти к шагу 5.

Шаг 5. Взять в качестве К разрез и найти наибольшую пропускную способность дуг в этом новом разрезе. (Текущее значение величины меньше, чем предыдущее, в силу определения множества на шаге 3 и множества дуг А на шаге 2.) Возвратиться к шагу 2.

Для неориентированных графов Франк и Фриш [16] предложили еще более простую процедуру нахождения пути с наибольшей пропускной способностью, состоящую в следующем.

Пусть некоторый -разрез, a Q - наибольшая пропускная способность ребер из Если теперь «закоротить» любое ребро с пропускной способностью т. е. вершины заменить одной вершиной положив

и ребро удалить, то получившийся граф будет иметь тот же самый путь с наибольшей пропускной способностью, что и первоначальный граф Справедливость этого утверждения вытекает из того факта, что является верхней границей для (в соответствии с (8.12)), и, следовательно, ребра с не могут повлиять на оптимальное решение, т. е. не могут войти в разрез К. Поскольку «закорачивание» ребра может повлиять только на разрезы, содержащие разрезы удаляются), то разрез К графа (или все разрезы, доставляющие минимум выражению (8.14), если их несколько) будет также и разрезом преобразованного графа

Процедуру, примененную к первоначальному графу можно повторить и для графа выбирая другой -разрез ,

закорачивая все ребра из пропускная способность которых не меньше наибольшей пропускной способности любого ребра из Это дает граф Процесс закончится, когда будут закорочены Теперь каждый -путь в графе образованный вершинами из и теми ребрами, которые оказались закороченными, будет иметь максимально возможную пропускную способность Ограничение на применимость данного алгоритма только к неориентированным графам вызвано именно процессом «закорачивания», так как при этом неявно предполагается, что путь с пропускной способностью, не меньшей, чем существует между любыми вершинами (двумя или большим числом), заменяемыми в описанном процессе единственной вершиной, но такое предположение может не выполняться, если закорачиваемые ребра имеют ориентацию.

Рис. 8.6а. Граф из примера 7.2.1.

Рис. 8.6б. Граф после первого стягивания.

Рис. 8.6в. Граф после второго стягивания.

Рис. 8.6г. Граф и путь с наибольшей пропускной способностью.

7.2.1. Пример.

Задача состоит в нахождении -пути (s) наибольшей пропускной способности в неориентированном графе, изображенном нет рис. 8.6а, где пропускные способности ребер указаны числами, стоящими у этих ребер.

Выбрав произвольно -разрез показанный на рис. 8.6а пунктиром, найдем, что ребром с максимальной пропускной способностью в К будет Закорачивая все ребра с пропускной способностью 16, получим граф изображенный на рис. 8.66. Выберем теперь -разрез графа так, как показано пунктиром на рис. 8.66. Наибольшая пропускная способность ребер в равна 14. Поэтому закорачиваем все ребра с пропускной способностью 214 и получаем граф изображенный на рис. 8.6в. Беря в качестве следующего -разрезa - он показан пунктиром на рис. 8.6в,- получаем а в

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

Окончательным графом будет остовный подграф графа содержащий лишь те ребра, которые закорачивались во время! описанной процедуры (т. е. только ребра Этог последний граф изображен на рис. и видно, что существует только один с наибольшей пропускной способностью. Этот путь показан жирными линиями, причем критическим ребром, этого пути будет с пропускной способностью 13.

Если требуется найти пути с наибольшей пропускной способностью между каждой парой вершин графа, то трехместную операцию из выражения (8.8) можно использовать в форме

поскольку так введенная операция удовлетворяет требованиям налагаемым соотношением (8.9). Начальной матрицей является исходная матрица пропускных способностей дуг (с нулевыми; элементами на местах отсутствующих дуг); конечная матрица дает пропускные способности путей между всеми парами: вершин.