Алгоритмы поиска остова во взвешенном графе: различия между версиями

== Постановка задачи ==

Вычисление t-остова наименьшего размера для заданного графа представляет собой важную комбинаторную задачу с множеством вариантов применения. Однако вычисление t-остова наименьшего размера для графа является NP-полной задачей. Фактически (для значений t > 2) NP-полной [10] является даже задача аппроксимации минимального размера t-остова для графа с коэффициентом O(2(1-) ln n) для любого  > 0. Осознав этот факт, исследователи предпочли двинуться в другом направлении, которое оказалось интересным и полезным. Пусть StG – размер наиболее разреженного t-остова графа G, а Stn – максимальное значение StG среди всех возможных графов с n вершинами. Существует ли алгоритм с полиномиальным временем исполнения, который для любого взвешенного графа и параметра t вычисляет его t-остов размера O(Stn)? Такой алгоритм был бы лучшим из того, на что мы могли бы надеяться, учитывая сложность исходной задачи t-остова. Возникает естественный вопрос: насколько велико может быть значение Stn? Из высказанной Эрдосом [12] 43 года назад гипотезы о нижней границе обхвата следует, что существуют графы с n вершинами, для которых 2k-остов и (2k–1)-остов состоят из (nl+l/k) дуг. Эта гипотеза была доказана для k = 1, 2, 3 и 5. Заметим, что (2k–1)-остов является также и 2k-остовом, а нижняя граница размера одинакова для 2k-остова и (2k–1)-остова. Таким образом, задача заключается в разработке алгоритма, который для любого взвешенного графа с n вершинами вычисляет (2k–1)-остов размера O(n1+1/k). Разумеется, хотелось бы найти самый быстрый алгоритм решения этой задачи, а наиболее амбициозная цель заключается в нахождении алгоритма линейной сложности.