Шаг 3. Выбрать такую вершину Xj*, что

Обновить данные: = U {xj*), = U ((а^., х'*)). Если \ Tg \ = п, то остановиться. Ребра в А^ образуют SST. Если \ Tg \Ф п, то перейти к шагу 4.

Шаг 4. Для всех Xj Т^, таких, что Xj 6 Г (ху*), обновить пометки следуюш,им образом.

Если Ру> с {Х]*, Xj), то положить Р; = с (Ху., Ху), tt; = Xf

и вернуться к шагу 3.

Если с (xj*, Xj), то перейти к шагу 3.

3.3. Родственные задачи

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

Более того, при доказательстве утверждения, связанного с операцией /, не используется тот факт, что полный вес остовного дерева равен сумме весов его ребер. Предполагалось только, что при замене ребра с весом С на ребро с весом С <iC вес дерева уменьшается.

Таким образом, если вес дерева представляет собой монотонно возрастающую симметричную функцию, зависящую от реберных весов, то остовное дерево, минимизирующее эту весовую функцию, должно быть тем же самым SST (которое минимизирует сумму весов ребер). Например, если С\, С^, . . ., - стоимости wi ребер графа G,TO остовным деревом графа G, минимизирующим С\ -Ь -f С?. 4- . . . -f Cf , или Ci, -Ci. ..... , где Cj d .. .,

Ci - веса каких-либо п - 1 ребер, образующих остовное дерево графа G, будет то же самое SST графа G. Добавим, что поскольку

*) Функция называется симметричной относительно переменных Xi,x2, . . ., ж^, если она не меняется при замене любой пары переменных друг на друга. Условия монотонности и симметричности диктуются тел, что при переходе от С к С < вес дерева должен уменьшаться.

В первой из упомянутых выше функций третью степень можно заменить на любую другую степень р > О и поскольку при р- оо

[ср]-{ max [CUP,

4=1 l l=i.....n-1 *

TO остовное дерево, у которого ребро с наибольшим весом имеет минимально возможный вес, совпадает с SST графа G.

3.4. Пример [48]

На графе G, изображенном на рис, 7.12, каждая вершина представляет некоторое лицо, а ребра (xj, xj) отражают тот факт, что лицо Xi может общаться с лицом Xj и наоборот. Требуется определить такой способ передачи конфиденциального сообщения между 12 лицами, ири котором вероятность утечки информации будет наименьшей. Каждой передаче сообщения от Xi к xj иринисы-вается некоторая вероятность р^ того, что послание может быть перехвачено носторонним лицом. Эти вероятности в процентах даны на рис. 7.12. Очевидно, что пути передачи сообщения должны образовывать остовное дерево графа G, и требуется найти такое остовное дерево, которое минимизирует величину 1 - П (1-р^у), где произведение берется по тем ребрам, которые образуют это дерево. Поскольку эта функция возрастающая и симметричная относительно р,/, то требуемое остовное дерево будет совпадать

Рис. 7.12. Граф из примера 3.4.

с, SST графа G, при этом р;, принимаются за стоимости ребер

Решим эту задачу, используя алгоритм из разд. 3.2.

Шаг 1. Возьмем х, = х^, Тх = {i}, Ai = 0.

Шаг 2. Примем за пометки для х^, х^ и х^;. [х^, 6], [xj. И] и [xi, 5] соответственно. Остальные пометки равны [О, оо].

Шаг 3. Наименьшая пометка Ру будет у вершины Xj, и поскольку as = Xi, то построим ребро (xi, Xg): = {xi, xg}, А^ = {(х^,

Хь)).

Шаг 4. Обновим пометки вершин Xg, Xg, x следующим образом:

для Ха : Рг = 6 < с (xs, Xg) и больше обновлять не надо;

для Хб : Рб = оо > с (xg, Хб) = 15, следовательно, пометка для Xg примет вид [xs, 15];

для Х7 : Ру = оо > с (xg, x) = 9 и пометка для ху примет значение [xg, 9].

Поскольку Х4 Г (xg), ее пометка останется такой же, как и на предыдущей итерации, т. е. [xi. И].

Шаг 3. Пометки теперь таковы: для х^ : [xi, 6], для Х4 : [xi, 11], для Хб : [xg, 15], для x : [xg, 9]. Наименьшая пометка Ру будет у Х2, и поскольку aj = Xi, то построено ребро (xi, Xj);

= {xi, Xg, Хг}, Al = {(xi, Xg), (xi, Хг)}.

Шаг 4. Аналогично обновим пометки вершин Хз, Х4, х^ следующим образом:

для Хз : [хг, 15],

для Х4 : [xi. И] (обновлять не надо),

для x : [xg 9] (обновлять не надо). Пометка для х^Т (х^) остается такой же, как и на предыдущей итерации, т. е. [xg, 15].

Шаг 3. Наименьшая пометка Ру будет у вершины х и поскольку a = Xg, ребро (xg, x) построено. = {х^, Xg, х^, х,}, A = = {{1, х^), (xi, Хг), (xg, Х7)}.

Шаг 4. Пометки вершин обновляются так же, как и раньше, и показаны на рис. 7.13а вместе с необходимыми для построения дерева дополнительными ребрами.

Продолжая таким образом, получим в конце SST, показанный на рис. 7.136, с номерами ребер, указывающими, в какой последовательности они вводились в дерево.

Произведение П (1 -- Р;у) для ребер этого дерева равно 0,5214, и, следовательно, величина минимума вероятности перехвата сообщения посторонним лицом равна 47,86 %.