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

Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 15: Строка 15:
В данной статье представлены два простейших алгоритма, вычисляющих (2k–1)-остов заданного взвешенного графа G = (V, E). Пусть n и m – число вершин и дуг графа G, соответственно. Первый алгоритм, разработанный Альтхофером и коллегами [2], основан на жадной стратегии и исполняется за время O(<math>mn^{1+1/k}</math>). Второй алгоритм [6] основан на сверхлокальном подходе, он исполняется за время O(km). Для начала рассмотрим следующее простое наблюдение. Предположим, что имеется подмножество <math>E_{s} \in E</math>, такое, что для каждой дуги <math>(x, y) \in E \setminus E_{s}</math> выполняется следующее утверждение.
В данной статье представлены два простейших алгоритма, вычисляющих (2k–1)-остов заданного взвешенного графа G = (V, E). Пусть n и m – число вершин и дуг графа G, соответственно. Первый алгоритм, разработанный Альтхофером и коллегами [2], основан на жадной стратегии и исполняется за время O(<math>mn^{1+1/k}</math>). Второй алгоритм [6] основан на сверхлокальном подходе, он исполняется за время O(km). Для начала рассмотрим следующее простое наблюдение. Предположим, что имеется подмножество <math>E_{s} \in E</math>, такое, что для каждой дуги <math>(x, y) \in E \setminus E_{s}</math> выполняется следующее утверждение.


Pt(x, y): вершины x и y связаны в подграфе (V, ES) путем, состоящим из не более чем t дуг, причем вес каждой дуги на этом пути не превышает вес дуги (x, y).
P<math>_{t}</math>(x, y): вершины x и y связаны в подграфе (V, E<math>_{S}</math>) путем, состоящим из не более чем t дуг, причем вес каждой дуги на этом пути не превышает вес дуги (x, y).
Из этого напрямую следует, что подграф (V, ES) будет t-остовом для G. Два алгоритма вычисления (2k–1)-остова способны вычислить множество ES при помощи двух совершенно разных подходов.
Из этого напрямую следует, что подграф (V, E<math>_{S}</math>) будет t-остовом для G. Два алгоритма вычисления (2k–1)-остова способны вычислить множество E<math>_{S}</math> при помощи двух совершенно разных подходов.


Алгоритм I
== Алгоритм I ==
Этот алгоритм выбирает дуги для остова по принципу жадности; он напоминает алгоритм Крускала для вычисления минимального остовного дерева. Дуги графа обрабатываются в порядке возрастания их весов. Начиная с остова ES = , алгоритм последовательно добавляет дуги. Решение о том, добавлять ли некоторую дугу (скажем, (u, v)) к ES или нет, принимается на основе следующего соображения:
Этот алгоритм выбирает дуги для остова по принципу жадности; он напоминает алгоритм Крускала для вычисления минимального остовного дерева. Дуги графа обрабатываются в порядке возрастания их весов. Начиная с остова <math>E_{S} = \varnothing</math>, алгоритм последовательно добавляет дуги. Решение о том, добавлять ли некоторую дугу (скажем, (u, v)) к E<math>_{S}</math> или нет, принимается на основе следующего соображения:
Если расстояние между u и v в подграфе, индуцированном текущими дугами остова ES, больше, чем t-weight(M, v), то дугу (u, v) следует добавить к to ES, в противном случае отбросить.
 
Из этого следует, что Pt(x, y) будет выполняться для каждой дуги E, не входящей в ES, так что в конце концов подграф (v, ES) будет представлять собой t-остов. Хорошо известное утверждение элементарной теории графов гласит, что граф с более чем n1+1/k дугами должен содержать цикл длиной не более 2k. Из приведенного выше алгоритма следует, что длина любого цикла в подграфе (V, ES) должна составлять не менее t + 1. Следовательно, для t = 2k – 1 количество дуг в подграфе (V, ES) будет менее n1+1/k. Таким образом, Алгоритм I вычисляет (2k–1)-остов размера O(n1+1/k), что является оптимальным, с учетом вышеупомянутой нижней границы.
''Если расстояние между u и v в подграфе, индуцированном текущими дугами остова E<math>_{S}</math>, больше, чем t-weight(M, v), то дугу (u, v) следует добавить к to E<math>_{S}</math>, в противном случае отбросить.''
Простая реализация Алгоритма I размера O(mn1+1/k) разработана на базе алгоритме Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем исполнения – O(kmn1/k). Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени исполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени исполнения.
 
Из этого следует, что P<math>_{t}</math>(x, y) будет выполняться для каждой дуги E, не входящей в E<math>_{S}</math>, так что в конце концов подграф (v, E<math>_{S}</math>) будет представлять собой t-остов. Хорошо известное утверждение элементарной теории графов гласит, что граф с более чем n1+1/k дугами должен содержать цикл длиной не более 2k. Из приведенного выше алгоритма следует, что длина любого цикла в подграфе (V, E<math>_{S}</math>) должна составлять не менее t + 1. Следовательно, для t = 2k – 1 количество дуг в подграфе (V, ES) будет менее n1+1/k. Таким образом, Алгоритм I вычисляет (2k–1)-остов размера O(n1+1/k), что является оптимальным, с учетом вышеупомянутой нижней границы.
Простая реализация Алгоритма I размера O(mn1+1/k) разработана на базе алгоритма Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем исполнения – O(kmn1/k). Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени исполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени исполнения.


Алгоритм II
Алгоритм II
Источник — http://pco.iis.nsk.su/wega/index.php/Алгоритмы_поиска_остова_во_взвешенном_графе