ВУЗ:
Составители:
Рубрика:
В. Ни одна из концевых вершин не принадлежит ни одному из
сформированных букетов. Если имеет место такой случай, то
необходимо окрасить ребро в синий цвет и сформировать но-
вый букет из его концевых вершин.
Г. Концевые вершины выбранного ребра принадлежат раз-
личным букетам. В этом случае необходимо окрасить вы-
бранное ребро в синий цвет, а оба букета, которым принадле-
жат его концевые вершины, слить в один новый букет.
Шаг 3. Если все вершины графа вошли в один букет, закончить
процедуру, так как при этом условии голубые ребра образуют
покрывающее дерево. В противном случае вернуться к началу
шага 2.
Пример 10.1.
Ребро Цвет
Букет
№ 1
Букет
№ 2
Пуст Пуст
(a,b)
Синий (1) {a,b} Пуст
(d,e)
Синий (2) {a,b} {d,e}
(a,d)
Синий (3) {a,b,d,e} Пуст
(b,e)
Оранжевый {a,b,d,e} Пуст
(e,c)
Синий (4) {a,b,d,e,c} Пуст
b a
c
e
d
В таблице показаны этапы построения покрывающего дерева.
Ребра графа рассматриваются в следующем произвольно выбран-
ном порядке: (a,b), (d,e), (a,d), (b,e), (e,c), (c,b), (a,c) и (с,d). Алго-
ритм заканчивается просмотром ребра (e,c), поскольку после этого
вершины рассматриваемого графа попадают в один букет. Четыре
голубых ребра (a,b), (d,e), (a,d) и (e,c) образуют для данного графа
покрывающее дерево (на рисунке ребра этого дерева выделены).
Рассмотренный алгоритм не учитывает веса ребер. Для реше-
ния задачи о слухах и аналогичных ей это и не нужно, так как в
этом случае достаточно ответить на вопрос, связен граф или нет. К
вопросу связности орграфов мы вернемся в лекции 14.
Лекция 11. Поиск на графах : алгоритмы поиска в глубину
и в ширину.
При решении прикладных задач часто возникает необходи-
мость обхода вершин графа, связанная с поиском вершин, удовле-
творяющих определенным свойствам. Например, необходимо от-
39
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »
