logo search
УП_САОД_2003

Нахождение минимального остовного дерева

Приведем без доказательства следующее свойство MST (minimal spanning tree – минимальное остовное дерево на английском языке).

В графе G = (V, E) рассмотрим U – некоторое подмножество V, такое что U и V\U не пусты. Пусть (u, v) – ребро наименьшей стоимости, одна вершина которого – u  U, а другая – v  V\U. Тогда существует некоторое MST, содержащее ребро (u, v).

Рисунок 57. Граф и его остовное дерево минимальной длины

На этом свойстве основаны два известных алгоритма.

        1.