7.3.1. Метод нахождения пути наибольшей приведенной пропускной способности

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

Сначала находим путь между имеющий наибольшую надежность. Пусть — пропускная способность этого пути, т. е.

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

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

Далее уже в графе ищется путь с наибольшей надежностью. Пропускная способность этого пути больше, чем но его надежность не превосходит надежности пути Если значение приведенной пропускной способности пути больше, чем значение этой величины для то берется как лучший путь и хранится до тех пор, пока не будет найден путь с большей приведенной пропускной способностью. Затем из А удаляется соответствующее множество дуг

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

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

Оптимальным путем будет текущий наилучший путь, полученный в конце описанной процедуры.

На эффективность вышеприведенного метода влияют два фактора.

Рис. 8.8. Граф из примера 7.3.2.

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

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

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