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

Из свойств разрезов и циклов следует, что в случае, если веса ребер уникальны, существует уникальное минимальное остовное дерево, которое мы обозначим MST(G). Уникальность всегда можно обеспечить, устраняя двусмысленность любым подходящим образом. Алгоритмы нахождения MST часто обращаются к полезному следствию свойств разрезов и циклов, называемому [[свойствомсжимаемости|свойством сжимаемости]]. Обозначим за G\C граф, полученный из исходного графа G путем сжатия подграфа C, при котором C заменяется единичной вершиной c, а все ребра, инцидентные ровно одной вершине в C, становятся инцидентными c; в общем случае G\C может содержать более одного ребра между двумя вершинами.

'''Свойство сжимаемости'''. Если C – подграф, такой, что для всех пар ребер e и f, имеющих ровно одну конечную точку в C, существует путь <math>P \subseteq C \;</math>, связывающий ef с каждым ребром в P, более легким, чем e или f, в таком случае С является сжимаемым. Для любого сжимаемого подграфа C верно <math>MST(G) = MST(C) \cup MST(G \backslash C) \;</math>.