ВУЗ:
Составители:
Рубрика:
37
Лекция 10. Построение покрывающих деревьев. Алгоритм
Краскала
.
На практике часто необходимо знать, связен ли данный граф.
Если граф не связен, то может потребоваться найти все его компо-
ненты. Приведем пример практической задачи, сводящейся к во-
просу о связности графа.
Задача
. В небольшой деревушке некоторые из жителей имеют
каждодневные встречи друг с другом. Может ли в этой деревне
распространиться какой-либо слух?
Чтобы ответить на этот вопрос, поставим в соответствие каж-
дому жителю деревни вершину графа. Соединим две вершины
ребром, если соответствующие жители ежедневно общаются друг
с другом. При условии связности полученного таким образом гра-
фа на поставленный в задаче вопрос можно ответить положитель-
но.
Построение покрывающих деревьев
Согласно определению покрывающее дерево существует толь-
ко для связных графов. Следовательно, если нам удалось постро-
ить хотя бы одно покрывающее дерево для данного графа, можно
сделать вывод, что он связный.
Рассмотрим алгоритм построения покрывающего дерева, пред-
ложенный Дж. Краскалом в 1957 г.
Суть алгоритма состоит в просмотре в заранее заданном поряд-
ке ребер исходного графа. При каждом просмотре в отношении
соответствующего ребра принимается решение о том, будет ли оно
включено в покрывающее дерево.
Алгоритм можно представить как процесс окрашивания ребер.
Пусть синий цвет используется для окраски ребер, включаемых в
покрывающее дерево, а оранжевый – для окраски ребер, не вклю-
чаемых в это дерево.
В алгоритме при рассмотрении ребра осуществляется лишь
проверка того, не образует ли данное ребро в совокупности с реб-
рами, уже включенными в дерево (ребрами, окрашенными в синий
цвет), цикл. Если результат проверки положителен, то рассматри-
ваемое ребро не включается в дерево (окрашивается в оранжевый
цвет). В противном случае ребро включается в дерево (окрашива-
ется в синий цвет).
В процессе работы алгоритма ребра, включенные в дерево, со-
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
