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