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

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

Из этого следует, что P<math>_{t}</math>(x, y) будет выполняться для каждой дуги E, не входящей в E<math>_{S}</math>, так что в конце концов подграф (v, E<math>_{S}</math>) будет представлять собой t-остов. Хорошо известное утверждение элементарной теории графов гласит, что граф с более чем <math>n^{1+\frac{1}{k}}</math> дугами должен содержать цикл длиной не более 2k. Из приведенного выше алгоритма следует, что длина любого цикла в подграфе (V, E<math>_{S}</math>) должна составлять не менее t + 1. Следовательно, для t = 2k – 1 количество дуг в подграфе (V, E<math>_{S}</math>) будет менее <math>n^{1+\frac{1}{k}}</math>. Таким образом, Алгоритм I вычисляет (2k–1)-остов размера <math>O(n^{1+\frac{1}{k}})</math>, что является оптимальным, с учетом вышеупомянутой нижней границы.

Простая реализация Алгоритма I размера <math>O(mn^{1+\frac{1}{k}})</math> разработана на базе алгоритма Дейкстры. Коэн [9], а впоследствии – Торуп и Цвик [18] разработали алгоритмы для (2k–1)-остова с улучшенным временем исполнения – <math>O(kmn^{\frac{1}{k}})</math>. Эти алгоритмы используют для вычисления расстояния несколько вызовов алгоритма Дейкстры нахождения кратчайших путей с единственным источником и в силу этого неспособны достичь линейного времени исполнения. С другой стороны, поскольку остов должен аппроксимировать расстояния между всеми парами вершин в графе, было бы сложно вычислить остов, избегая получения явной информации о расстояниях. Как ни удивительно, Алгоритм II успешно избегает каких-либо вычислений расстояния и достигает почти линейного времени исполнения.