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

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