Алгоритмы построения покрывающих деревьев
Рассмотрим граф G(X,E),
в котором направление дуг не задаётся
(т.е. это неориентированный граф).
Предположим, что каждому ребру
этого графа приписан вес
.
Определим вес покрывающего дерева, как
сумму весов составляющих его рёбер.
Пример1 (иллюстрационный):
В управлении шоссейных дорог рассматривается проект строительства новых дорог, которые должны связать пять городов некоторого района. Стоимость прокладки дороги между каждой парой городов известна.
|
a |
b |
c |
d |
e |
a |
× |
5 |
50 |
80 |
90 |
b |
5 |
× |
70 |
60 |
50 |
c |
50 |
70 |
× |
8 |
20 |
d |
80 |
60 |
8 |
× |
10 |
e |
90 |
50 |
20 |
10 |
× |
Построим граф, вершины которого соответствуют городам, а рёбра – дорогам, которые могут быть проложены между определёнными городами. Каждому ребру приписан вес разной стоимости проекта строительства дороги.
Составление строительства дорог и городов теперь можно свести к задаче построения для графа покрывающего дерева минимальной стоимости.
Алгоритм можно представить как процесс окрашивания рёбер. При этом голубой цвет используется для окраски рёбер, включаемых при окраске дерева, а оранжевый – для окраски рёбер, не включаемых при окраске дерева.
При алгоритме окрашивания ребра осуществляется лишь проверка того, не образуется ли данное дерево в совокупности с уже включёнными рёбрами в дерево цикла.
Если результат проверки является положительным, то рассматриваемое ребро не включается в дерево, окрашивается в оранжевый цвет. В противном случае, ребро включается в дерево и окрашивается в голубой цвет.
Проверка на наличие цикла осуществляется так: проверяется, принадлежат ли обе концевые вершины одной и той же компоненты связности, которую ещё называют “букетом”. Работа алгоритма заканчивается, когда количество окрашенных рёбер в голубой цвет окажется на единицу меньше числа вершин или когда все вершины окажутся в одном букете.
Алгоритм построения покрывающего дерева славик?!! последняя :-(