Минимальное остовное дерево: различия между версиями

Перейти к навигации Перейти к поиску
Строка 13: Строка 13:


== Условия оптимальности ==
== Условия оптимальности ==
Разрез представляет собой разбиение (V0; V00) вершин V. Ребро (u, v) пересекает разрез (V, V"), если u 2 V и v 2 V00. Последовательность (v0; v1,.: ; v Vjt_i; v0) является циклом, если (vi ; vi+1(mod k)) 2 £ для 0 < i < k.
[[Разрез]] представляет собой разбиение (V', V") вершин графа V. Ребро (u, v) пересекает разрез (V, V"), если <math>u \in V' \;</math> и <math>v \in V'' \;</math>. Последовательность <math>(v_0, v_1,..., v_{k-1}, v_0) \;</math> является циклом, если <math>(v_i, v_{i+1(mod k)}) \in E \;</math> для <math>0 \le i < k \;</math> .
 
Корректность всех алгоритмов нахождения MST устанавливается при помощи двух свойств, разрезов и циклов, также известных как синее и красное правила [18].
Корректность всех алгоритмов нахождения MST устанавливается при помощи двух свойств, разрезов и циклов, также известных как синее и красное правила [18].


Строка 23: Строка 24:


Свойство сжимаемости. Если C – подграф, такой, что для всех пар ребер e и f, имеющих ровно одну конечную точку в C, существует путь P С C, связывающий ef с каждым ребром в P, более легким, чем e или f, в таком случае С является сжимаемым. Для любого сжимаемого подграфа C верно MST(G) = MST(C) [ MST(G n C).
Свойство сжимаемости. Если C – подграф, такой, что для всех пар ребер e и f, имеющих ровно одну конечную точку в C, существует путь P С C, связывающий ef с каждым ребром в P, более легким, чем e или f, в таком случае С является сжимаемым. Для любого сжимаемого подграфа C верно MST(G) = MST(C) [ MST(G n C).


== Базовый жадный алгоритм ==
== Базовый жадный алгоритм ==