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

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

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