4551
правка
Алгоритмы поиска остова во взвешенном графе: различия между версиями
Материал из WEGA
Алгоритмы поиска остова во взвешенном графе (посмотреть исходный код)
Версия от 17:18, 17 декабря 2011
, 17 декабря 2011нет описания правки
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)-остов состоят из | размер наиболее разреженного 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^{l+l/k})</math> дуг. Эта гипотеза была доказана для k = 1, 2, 3 и 5. Заметим, что (2k–1)-остов является также и 2k-остовом, а нижняя граница размера одинакова для 2k-остова и (2k–1)-остова. Таким образом, задача заключается в разработке алгоритма, который для любого взвешенного графа с n вершинами вычисляет (2k–1)-остов размера <math>O(n^{1+1/k})</math>. Разумеется, хотелось бы найти самый быстрый алгоритм решения этой задачи, а наиболее амбициозная цель заключается в нахождении алгоритма линейной сложности. | ||
== Основные результаты == | |||
В данной статье представлены два простейших алгоритма, вычисляющих (2k–1)-остов заданного взвешенного графа G = (V, E). Пусть n и m – число вершин и дуг графа G, соответственно. Первый алгоритм, разработанный Альтхофером и коллегами [2], основан на жадной стратегии и исполняется за время O(mn1+1/k). Второй алгоритм [6] основан на сверхлокальном подходе, он исполняется за время O(km). Для начала рассмотрим следующее простое наблюдение. Предположим, что имеется подмножество ES E, такое, что для каждой дуги (x;y) E\ES выполняется следующее утверждение. | В данной статье представлены два простейших алгоритма, вычисляющих (2k–1)-остов заданного взвешенного графа G = (V, E). Пусть n и m – число вершин и дуг графа G, соответственно. Первый алгоритм, разработанный Альтхофером и коллегами [2], основан на жадной стратегии и исполняется за время O(mn1+1/k). Второй алгоритм [6] основан на сверхлокальном подходе, он исполняется за время O(km). Для начала рассмотрим следующее простое наблюдение. Предположим, что имеется подмножество ES E, такое, что для каждой дуги (x;y) E\ES выполняется следующее утверждение. | ||
