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

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


'''Свойство разрезов'''. Ребро принадлежит к некоторому минимальному остовному дереву в том и только том случае, если это самое легкое ребро, пересекающее некоторый разрез.
'''Свойство разрезов'''. Ребро принадлежит к некоторому минимальному остовному дереву в том и только том случае, если это самое легкое ребро, пересекающее некоторый разрез.


'''Свойство циклов'''. Ребро не принадлежит ни к одному минимальному остовному дереву в том и только том случае, если это единственное самое тяжелое ребро в некотором цикле.
'''Свойство циклов'''. Ребро не принадлежит ни к одному минимальному остовному дереву в том и только том случае, если это единственное самое тяжелое ребро в некотором цикле.




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