Введение
Проблема поиска k минимальных остовных деревьев, изучаемая в теоретической информатике, заключается в нахождении дерева минимальной стоимости, содержащего ровно k вершин и являющегося подграфом большего графа. Она также известна как k MST или остовное дерево кардинальности k с весами на ребрах. Поиск такого дерева является NP-трудной задачей, однако его можно аппроксимировать с постоянным коэффициентом аппроксимации за полиномиальное время.
Заявление о проблеме
Входные данные для задачи состоят из неориентированного графа с весами на ребрах. Выходные данные – дерево с k вершинами и k − 1 ребром, при этом все ребра выходного дерева должны принадлежать входному графу. Стоимость дерева – это сумма весов его ребер, и цель состоит в том, чтобы найти дерево с минимальной стоимостью. Задача была сформулирована и . Рави и др. также рассматривали геометрическую версию задачи, которую можно рассматривать как частный случай графовой задачи. В геометрической задаче о минимальном остовном дереве на k точках входными данными является множество точек на плоскости. Снова, выходные данные должны представлять собой дерево, в качестве вершин которого используются k точек, минимизирующее общую евклидову длину его ребер. Иными словами, это задача о минимальном остовном дереве на k вершинах на полном графе с евклидовыми расстояниями в качестве весов.
Ravi et al. also considered a geometric version of the problem, which can be seen as a special case of the graph problem. In the geometric k minimum spanning tree problem, the input is a set of points in the plane. Again, the output should be a tree with k of the points as its vertices, minimizing the total Euclidean length of its edges. That is, it is a graph k minimum spanning tree on a complete graph with Euclidean distances as weights.
Комплексность вычислений
Когда k является фиксированной константой, задача о k минимальных остовных деревьях может быть решена за полиномиальное время алгоритмом полного перебора, перебирающим все k-элементные наборы вершин. Однако, для переменного k, задача о k минимальных остовных деревьях была показана NP-трудной посредством сведения из задачи о дереве Штейнера. То же самое справедливо и для задачи о k минимальных остовных деревьях. Лучшее известное приближение для общей задачи достигает коэффициента приближения 2 и основано на примально-дуальной схеме. Когда входные данные состоят из точек на евклидовой плоскости (любые две из которых могут быть соединены в дереве со стоимостью, равной расстоянию между ними), существует полиномиальная схема аппроксимации, разработанная.