Алгоритмы поиска остова во взвешенном графе: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 9: | Строка 9: | ||
Вычисление t-остова наименьшего размера для заданного графа представляет собой важную комбинаторную задачу с множеством вариантов применения. Однако вычисление t-остова наименьшего размера для графа является NP-полной задачей. Фактически (для значений t > 2) NP-полной [10] является даже задача аппроксимации минимального размера t-остова для графа с коэффициентом O(2<math>^{(1-\mu ) ln n)}</math>) | Вычисление 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> – | для любого <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^{ | размер наиболее разреженного 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+1/k})</math> дуг. Эта гипотеза была доказана для k = 1, 2, 3 и 5. Заметим, что (2k–1)-остов является также и 2k-остовом, а нижняя граница размера одинакова для 2k-остова и (2k–1)-остова. Таким образом, задача заключается в разработке алгоритма, который для любого взвешенного графа с n вершинами вычисляет (2k–1)-остов размера O(<math>n^{1+1/k}</math>). Разумеется, хотелось бы найти самый быстрый алгоритм решения этой задачи, а наиболее амбициозная цель заключается в нахождении алгоритма линейной сложности. | ||
== Основные результаты == | == Основные результаты == | ||