4551
правка
Минимальное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальное остовное дерево (посмотреть исходный код)
Версия от 17:11, 22 декабря 2015
, 22 декабря 2015→Условия оптимальности
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> . | [[Разрез]] представляет собой разбиение (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]. | ||
Свойство циклов. Ребро не принадлежит ни к одному минимальному остовному дереву в том и только том случае, если это единственное самое тяжелое ребро в некотором цикле. | '''Свойство разрезов'''. Ребро принадлежит к некоторому минимальному остовному дереву в том и только том случае, если это самое легкое ребро, пересекающее некоторый разрез. | ||
'''Свойство циклов'''. Ребро не принадлежит ни к одному минимальному остовному дереву в том и только том случае, если это единственное самое тяжелое ребро в некотором цикле. | |||
Из свойств разрезов и циклов следует, что в случае, если веса ребер уникальны, существует уникальное минимальное остовное дерево, которое мы обозначим MST(G). Уникальность всегда можно обеспечить, устраняя двусмысленность любым подходящим образом. Алгоритмы нахождения MST часто обращаются к полезному следствию свойств разрезов и циклов, называемому свойством сжимаемости. Обозначим за GnC граф, полученный из исходного графа G путем сжатия подграфа C, при котором C заменяется единичной вершиной c, а все ребра, инцидентные ровно одной вершине в C, становятся инцидентными c; в общем случае GnC может содержать более одного ребра между двумя вершинами. | Из свойств разрезов и циклов следует, что в случае, если веса ребер уникальны, существует уникальное минимальное остовное дерево, которое мы обозначим MST(G). Уникальность всегда можно обеспечить, устраняя двусмысленность любым подходящим образом. Алгоритмы нахождения MST часто обращаются к полезному следствию свойств разрезов и циклов, называемому свойством сжимаемости. Обозначим за GnC граф, полученный из исходного графа G путем сжатия подграфа C, при котором C заменяется единичной вершиной c, а все ребра, инцидентные ровно одной вершине в C, становятся инцидентными c; в общем случае GnC может содержать более одного ребра между двумя вершинами. | ||
Свойство сжимаемости. Если 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). | |||
== Базовый жадный алгоритм == | == Базовый жадный алгоритм == | ||