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

Поскольку остовные графы с меньшим числом ребер обеспечивают более эффективное построение минимального остовного дерева, мощность остовного графа определяется как количество ребер в нем. Легко увидеть, что полный граф на множестве точек содержит все остовные деревья и, в силу этого, является остовным графом. Однако мощность подобного графа составляет <math>O(n^2) \;</math>. Прямолинейный остовный граф мощности O(n) может быть построен за время O(n log n) [6].

Алгоритмы построения МОД обычно используют два свойства, позволяющие включать ребра в минимальное остовное дерево и исключать их. Первое свойство, известное как [[свойство разрезов]], гласит, что ребро с минимальным весом, пересекающее любое разбиение множества вершин на два подмножества, принадлежит к МОД. Второе свойство называется [[свойство циклов|свойством циклов]] и утверждает, что ребро любого цикла графа, имеющее наибольший вес, можно безопасно удалить. Поскольку эти два свойства сформулированы в контексте построения минимального остовного дерева, они оказываются полезными для остовного графа.