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

Задача нахождения минимального остовного дерева (MST) заключается в следующем: имеется связный взвешенный неориентированный граф G = (V, E, w), необходимо найти дерево с минимальным общим весом, содержащее все вершины из V. Здесь <math>w: \mathbb{E} \Rightarrow \mathbb{R} \;</math> – весовая функция. Задачу часто формулируют в геометрических терминах, где V – множество точек в d-мерном пространстве, а w соответствует евклидову расстоянию. Основное различие между двумя подходами заключается в виде входных данных. В графовой формулировке входной граф имеет размер O(m + n) и состоит из перечисления n = |V| вершин и m = |E| ребер, а также весов ребер. В геометрической формулировке на входе имеется перечисление координат каждой точки (пространство O(dn) ): все <math>\left ( \frac{V}{2} \right ) \;</math> ребер представлены неявно, веса неявно приписаны к координатам точек. В [16] обсуждается задача нахождения минимального евклидова остовного дерева.