Остов графа (покрывающее дерево)

— это подграф, содержащий все вершины. Остовный подграф, являющийся деревом,

называется остовом или каркасом (лес).
Букет – множество вершин, принадлежащих одной компоненте связности.

дерево;
оранжевым цветом окрашиваются ребра, не включаемые в покрывающее дерево, т.к.

они образуют цикл с синими ребрами или являются петлями.

Существует 2 случая связности графа:
1 Если G (V,E) – связный граф, то построение покрывающего дерева по алгоритму Краскала заканчивается, когда количество ребер, окрашенных в синий цвет, становится равным (p-1) .
2 Если G (V,E) – несвязный граф, то построение покрывающего дерева по алгоритму Краскала заканчивается после раскраски всех ребер графа. Число покрывающих деревьев в таком лесу будет равно числу букетов.

один
из букетов не формирован.

Шаг 1. Все петли окрасить в оранжевый

цвет.
Шаг 2. Из упорядоченного множества E выбирается первое
ребро, не являющееся петлей. Это ребро окрашивается в синий цвет и формируется букет, в который включаются концевые вершины выбранного ребра.
Шаг 3. Из оставшихся ребер выбирается первое неокрашенное ребро, которое не является петлей. Если в графе такого ребра нет, следует закончить процедуру и перейти к шагу 4.
Шаг 4. Если все ребра окрашены, следует закончить процедуру. Синие ребра образуют покрывающее дерево (лес). В противном случае вернуться к началу шага 2.

вершины выбранного ребра принадлежат одному и тому же букету. В

этом случае ребро окрашивается в оранжевый цвет.
Б. Одна из концевых вершин ребра принадлежит существующему букету, а другая – не принадлежит ни одному из уже сформированных букетов. В этом случае ребро окрашивается в синий цвет, и его вторая концевая вершина включается в букет, которому принадлежит первая концевая вершина.
В. Концевые вершины выбранного ребра принадлежат
различным букетам. В этом случае ребро окрашивается в синий цвет, а оба букета, которым принадлежат его концевые вершины, объединяем в новый букет с меньшей нумерацией.
Г. Ни одна из концевых вершин не принадлежит ни одному из формированных букетов. В этом случае ребро окрашивается в синий цвет и формируется новый букет из концевых вершин этого ребра.

в порядке возрастания длин.
Выход: множество T рёбер кратчайшего остова.

T = {}
k = 1 { номер рассматриваемого ребра }
for i from 1 to p-1 do
while (T + E[k]) - цикл do
k = k + 1 { пропустить это ребро }
T= T + Е[k] { добавить это ребро в остов }
k = k + 1
end

ребра упорядочены по возрастанию весов и по
нумерации для ребер с

одинаковыми весами. Петли удалены. Из кратных ребер оставляем ребро с минимальным весом.
Минимальное покрывающее дерево T не построено.
Букет не сформирован.

Шаг 1. Выбираем из упорядоченного множества E первое
ребро (i,j) и включаем его в дерево T .
Обе концевые вершины включаем в букет { i, j} .
Удаляем из E выбранное ребро.

Шаг 2. Из множества E выбираем первое ребро, инцидентное какой-либо вершине из сформированного букета.

существующими ребрами
дерева. Тогда удаляем его из E и возвращаемся к
началу

шага 2.
Б. Ребро не образует с существующими ребрами дерева
цикл. Тогда новая вершина добавляется к вершинам
сформированного букета. Ребро добавляется в дерево. Далее возвращаемся к началу шага 2.

Шаг 3. Если дерево (букет) включает в себя все вершины графа,
то минимальное покрывающее дерево построено.
(Если дерево не включает в себя все вершины, то граф не является связным.)

остов, b[v] — это длина ребра, соединяющего v с остовом.

Если вершину v ещё нельзя соединить с остовом одним ребром, то a[v]: = 0, b[v]: = .

Вход: граф G(V, E), заданный матрицей длин рёбер С.
Выход: множество Т рёбер кратчайшего остова.

- множество вершин, включённых в кратчайший остов }
T =

 { T - множество рёбер, включённых в кратчайший остов }
for v  V - u do
if v Г(u) then
a[v]: = u { u — ближайшая вершина остова }
b[v]: = С[u, v] { C[u, v] — длина соответствующего ребра }
else
a[v]: = 0 { ближайшая вершина остова неизвестна }
b[v]: =  { и расстояние также неизвестно }
end if
end for

х: =  {начальное значение для поиска ближайшей вершины}

for v  V \ S do
if b[v] < х then
w = v { нашли более близкую вершину }
x = b[v] { и расстояние до неё }
end if
end for
S = S + w { добавляем найденную вершину в остов }
T =T + (a[w],w) { добавляем найденное ребро в остов }
for v  Г(w) do
if v  S then
if b[v] >C[v,w] then
a[v]: = w { изменяем ближайшую вершину остова }
b[v]: = C[v, w] { и длину ведущего к ней ребра }
end if
end if
end for end for