double arrow

Построение покрывающих деревьев

Исходя из определения покрывающего дерева, можно сделать вывод, что оно существует только для связных графов. То есть если нам удалось построить хотя бы одно покрывающее дерево для данного графа, можно сделать вывод, что он связный.

Рассмотрим алгоритм построения покрывающего дерева, предложенный Дж. Краскалом в 1957 г.

Суть алгоритма состоит в просмотре в произвольном порядке рёбер исходного графа. При каждом просмотре в отношении соответствующего ребра принимается решение о том, будет или не будет оно включено в покрывающее дерево.

Алгоритм можно представить как процесс окрашивания рёбер. Пусть голубой цвет используется для окраски рёбер, включаемых в покрывающее дерево, а оранжевый – для окраски рёбер, не включаемых в это дерево.

В алгоритме при рассмотрении ребра осуществляется лишь проверка того, не образует ли данное ребро в совокупности с рёбрами, уже включенными в дерево (рёбрами, окрашенными в голубой цвет), цикл. Если результат проверки является положительным, то рассматриваемое ребро не включается в дерево (окрашивается в оранжевый цвет). В противном случае это ребро включается в дерево (окрашивается в голубой цвет).

В процессе работы алгоритма рёбра, включенные в дерево, составляют граф, имеющий один или несколько связных компонентов. Множество вершин, принадлежащих отдельному связному компоненту, для сокращения речи будем называть “букетом”. Некоторое ребро образует цикл с рёбрами, уже включенными в дерево, если обе его концевые вершины принадлежат одному и тому же связному компоненту (одному и тому же букету).

Работа алгоритма по построению покрывающего дерева заканчивается, когда количество рёбер, окрашенных в голубой цвет, становится равным числу, на единицу меньшему числа вершин графа, или, что то же самое, когда все вершины графа оказываются в одном букете.

Оба условия выхода относятся к случаю, когда исходный граф содержит покрывающее дерево, то есть является связным.

Если граф не является связным, то алгоритм заканчивается после раскраски всех рёбер графа. Голубые рёбра образуют покрывающий лес. Число деревьев в полученном лесе равно числу оставшихся букетов.

Сформулируем алгоритм построения покрывающего дерева.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: