графа 
при этом 
принимаются за «стоимости» ребер 
Решим эту задачу, используя алгоритм из разд. 3.2.
Шаг 1. Возьмем 
Шаг 2. Примем за пометки для 
и 
соответственно. Остальные пометки равны 
Шаг 3. Наименьшая пометка 
будет у вершины 
и поскольку 
то построим ребро 
Шаг 4. Обновим пометки вершин 
следующим образом:
для 
и больше обновлять не надо;
для 
следовательно, пометка для 
примет вид 
;
для 
и пометка для 
примет значение 
Поскольку 
ее пометка останется такой же, как и на предыдущей итерации, т. е. 
Шаг 3. Пометки теперь таковы: для 
для 
, для 
для 
Наименьшая пометка 
; будет 
и поскольку 
то построено ребро 
Шаг 4. Аналогично обновим пометки вершин 
следующим образом:
для 
(обновлять не надо),
для 
(обновлять не надо).
Пометка для 
остается такой же, как и на предыдущей итерации, т. е. 
.
Шаг 3. Наименьшая пометка 
будет у вершины 
и поскольку 
ребро 
построено. 
Шаг 4. Пометки вершин обновляются так же, как и раньше, и показаны на рис. 7.13а вместе с необходимыми для построения дерева дополнительными ребрами.
Продолжая таким образом, получим в конце SST, показанный на рис. 7.136, с номерами ребер, указывающими, в какой последовательности они вводились в дерево.
Произведение 
для ребер этого дерева равно 0,5214, и, следовательно, величина минимума вероятности перехвата сообщения посторонним лицом равна 
Рис. 7.13а. Частично сформированное дерево с пометками на вершинах, не принадлежащих Тх. 
Надо добавить следующее ребро.
Рис. 7.13б. SST графа на рис. 7.12.
изображенном на рис. 7.12, каждая вершина представляет некоторое лицо, а ребра 
отражают тот факт, что лицо 
может общаться с лицом 
и наоборот. Требуется определить такой способ передачи конфиденциального сообщения между 12 лицами, при котором вероятность утечки информации будет наименьшей. Каждой передаче сообщения от 
приписывается некоторая вероятность 
того, что послание может быть перехвачено посторонним лицом. Эти вероятности в процентах даны на рис. 7.12. Очевидно, что пути передачи сообщения должны образовывать остовное дерево графа 
и требуется найти такое остовное дерево, которое минимизирует величину 
где произведение берется по тем ребрам, которые образуют это дерево. Поскольку эта функция возрастающая и симметричная относительно 
то требуемое остовное дерево будет совпадать
