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

[[Остов]] – это ''разреженный'' [[подграф]] данного [[неориентированный граф|неориентированного графа]], сохраняющий приближенные расстояния между каждой парой вершин. Более точно, t-остов графа <math>G = (V, E)\, </math> представляет собой подграф <math>(V, E_{s}), E_{s} \subseteq E \, </math>, такой, что для любой пары вершин расстояние между ними в подграфе не более чем в t раз больше расстояния между ними в исходном графе; при этом t называется [[коэффициент растяжения|коэффициентом растяжения]]. Формальное определение остовам дали Пелег и Шеффер [14], хотя связанные с ними понятия неявно использовал Авербух [3] в контексте сетевых синхронизаторов.

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