Минимальное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
== Условия оптимальности == | == Условия оптимальности == | ||
Разрез представляет собой разбиение ( | [[Разрез]] представляет собой разбиение (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). | ||
== Базовый жадный алгоритм == | == Базовый жадный алгоритм == | ||