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

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

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

= min [Qij],

При этом через будет обозначаться также и множество дуг, образующих рассматриваемый путь. Если из А удалить множество дуг Ао = {{Xi, Xj) \{Xi, Xj) 6 A, Qij-Q} и образовать множество A = A - 0, TO либо граф G == (X, A), являющийся остовным подграфом графа G, содержит оптимальный путь из G, либо Р^ будет оптимальным путем. Это можно обосновать так.

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

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

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

Ai = {{xi, Xj)\{Xi, Xj)£A, QijQ-}.

Получается множество А = А' - Ai и остовный подграф G = = (X, А ). По тем же самым причинам, что и выше, либо граф G содержит оптимальный путь, либо оптимальным будет наилучший из найденных до данного момента путь. Этот процесс продолжается до тех пор, пока не получится остовный подграф G\ удовлетворяющий одному из следующих условий: либо он является несвязным.

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

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

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

(6,0,6) 4

(16,0,4)

!,0,9)

j(9,0,8)/<rfb

(12,0,7)

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

гпучае, когда на каждом этапе наиболее надежный путь испопь зует дугу с наименьшей пропускной способностью, понадобитсн т - к этапов (для нахождении пути с наилучшей надежностью). где т - число дут в G и А; - число дуг в оптимальном пути Самым хорошим случаем будет тот, когда уже первый остовный подграф' G является несвязным и вершины s и f находятся ъ раг'чых ком понентах. Тогда потребуется только один этап

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

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

7.3.2. Пример. Найти путь от s к < с наибольшей приведенной пропускной способностью в графе G, изображенном на рис. 8.8, где каждая дуга имеет пометку (а, Ь), причем а является пропускной способностью дуги, а b - ее надежностью.

(14,0,8) 06,0,4)

Jfj (12,0.7) Xj Рис. 8.9a. Граф G из примера 7.3.2.

06.0,4)

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