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

[[Остов]] – это ''разреженный'' [[подграф]] данного [[неориентированный граф|неориентированного графа]], сохраняющий приближенные расстояния между каждой парой вершин. Более точно, 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>. Разумеется, хотелось бы найти самый быстрый алгоритм решения этой задачи, а наиболее амбициозная цель заключается в нахождении алгоритма линейной сложности.

В данной статье представлены два простейших алгоритма, вычисляющих (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): вершины x и y связаны в подграфе (V, E<math>_{S}</math>) путем, состоящим из не более чем t ребер, причем вес каждого ребра на этом пути не превышает вес ребра (x, y).

Этот алгоритм выбирает ребра для остова по принципу жадности; он напоминает алгоритм Крускала для вычисления минимального остовного дерева. Ребра графа обрабатываются в порядке возрастания их весов. Начиная с остова <math>E_{S} = \varnothing</math>, алгоритм последовательно добавляет ребра. Решение о том, добавлять ли некоторое ребро (скажем, <math>(u, v) \, </math>) к <math>E_{S} \, </math> или нет, принимается на основе следующего соображения:

 

 

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

Пусть даны взвешенный граф G = (V, E) и целое число k > 1. Остов с коэффициентом растяжения (2k–1) и размером <math>O(kn^{1+\frac{1}{k}})</math> может быть вычислен за время O(km).

Алгоритм выполняется в O(k) этапов; на каждом этапе он вычисляет список смежности для каждой вершины с целью отсечения необязательных ребер. Для доказательства простоты алгоритма далее приводятся его полная версия для нахождения 3-остова и анализ алгоритма. Алгоритм может быть легко адаптирован к другим вычислительным моделям (с параллельной, внешней или распределенной памятью) с сохранением почти оптимальной производительности (подробнее см. в [6]).

Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> ребер. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их ребра могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на [[доминирующее множество|доминирующих множествах]].

Вначале имеется множество ребер E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает ребра E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа.

(a) Если v не является смежной с какой-либо выбранной вершиной, то каждое ребро, инцидентное v, перемещается в E<math>_{S}</math>.

(b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего к v соседа из числа выбранных вершин (связи можно разрывать произвольным образом; однако ради удобства можно считать, что все веса различны.). Ребро (v , N(v, R)) и каждое инцидентное v ребро с весом, меньшим, чем у этого ребра, перемещаются в E<math>_{S}</math>. Затем вершина v добавляется в кластер с центром в N(v, R).

На последнем шагу первого этапа все ребра (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются.

Пусть V’ – множество вершин, соответствующих конечным точкам ребер E’, оставшимся после завершения первого этапа. Из этого следует, что каждая вершина из V’ является либо вершиной из выборки, либо смежной с одной из таких вершин, и этап 1(b) разбивает V' на непересекающиеся кластеры, в центре каждого из которых находится некоторая вершина из выборки. Заметим, что вследствие последнего этапа каждое ребро в множестве E’ является внутрикластерным ребром. Граф (V’, E’) т соответствующее разбиение V’ на кластеры передается на вход следующего (второго) этапа.

Пусть E’(v, c) – ребра из множества E’, инцидентные v, из кластера c. Для каждого кластера c, являющегося соседом v, ребро из E’(v, c) с наименьшим весом перемещается в E<math>_{S}</math>; остальные ребра отбрасываются.

Количество ребер, добавленных к остову E<math>_{S}</math> за время выполнения описанных этапов алгоритма, можно ограничить следующим образом. Заметим, что множество выборки R формируется путем случайного и независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Из элементарной вероятности следует, что для каждой вершины <math>v \in V</math> ожидаемое количество инцидентных ей ребер с весами меньше, чем у (v, N (v, R)), не превосходит <math>\sqrt{n}</math>. Таким образом, ожидаемое количество ребер, вносимых в остов каждой вершиной на первом этапе алгоритма, не превосходит <math>\sqrt{n}</math>. Количество ребер, добавленных к остову на второй фазе, составляет O(n<math>\mid</math>R<math>\mid</math>). Поскольку ожидаемый размер выборки R равен <math>\sqrt{n}</math>, следовательно, ожидаемое количество ребер, добавленных к остову на второй фазе, составляет не более n<math>^{3/2}</math>. Следовательно, ожидаемый размер остова E<math>_{S}</math> по окончании работы Алгоритма II в вышеописанном виде не превосходит 2n<math>^{3/2}</math>. Алгоритм выполняется повторно, если размер остова превосходит 3n<math>^{3/2}</math>. Из неравенства Маркова следует, что ожидаемое количество таких повторений будет составлять O(1).

Установим теперь, что E<math>_{S}</math> является 3-остовом. Заметим, что для каждого ребра edge (u, v) <math>\notin</math> E<math>_{S}</math>, вершины u и v на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев.

Пусть u и v принадлежат к одному кластеру с центром x <math>\in</math> R. Из первой фазы алгоритма следует, что существует путь из двух ребер u – x – v в остове, причем каждое из этих ребер не тяжелее ребра (u, v). (Этот факт дает обоснование для отбрасывания всех внутрикластерных ребер в конце первого этапа).

Очевидно, что ребро (u, v) была удалена из E’ на этапе 2; предположим, что она была удалена при обработке вершины u. Пусть вершина v входит в кластер с центром x <math>\in</math> R.

 

Пусть в начале второго этапа (u, v’) <math>\in</math> E’ будет ребром с наименьшим весом среди всех ребер, инцидентных u, от вершин кластера с центром в x. Таким образом, должно выполняться weight(u, v’) ≤ weight(u, v). Обработка вершины u на втором этапе алгоритма гарантирует, что ребро (u, v’) добавляется в E<math>_{S}</math>. Следовательно, существует путь Π<math>_{uv}</math> = u – v’ – x – v между u и v в остове E<math>_{S}</math>, и его вес ограничен weight(Π<math>_{uv}</math>) = weight(u, v’) + weight(v’, x) + weight(x, v). Поскольку (v’, x) и (v, x) были выбраны на первом этапе, должно выполняться weight(v’, x) ≤ weight(u, v’) и weight(x, v) ≤ weight(u, v). Отсюда следует, что остов (v, E<math>_{S}</math>) имеет коэффициент растяжения 3. Кроме того, обе фазы алгоритма могут быть выполнены за время O(m) с использованием элементарных структур данных и блочной сортировки.

Алгоритм вычисления (2k–1)-остова выполняет k итераций, причем каждая итерация напоминает первый этап алгоритма нахождения 3-остова. Детали и формальное доказательство можно найти в [6].

Среди других интересных вариантов остовов – ''остов с сохранением расстояния'', предложенный Боллобасом и коллегами [8], и ''легковесный остов'', предложенный Авербухом и коллегами [4]. Подграф называется d-хранителем, если он сохраняет точные расстояния между каждой парой вершин, разделенных расстоянием не менее d. Легковесный остов стремится минимизировать количество ребер и полный вес ребер. Параметр «''легкость''» определяется для подграфа как отношение полного веса всех его ребер к весу минимального остовного дерева графа. Авербух и коллеги [4] показали, что для любого взвешенного графа и целого числа k > 1 существует O(k)-остов с <math>O(k \rho n^{l+\frac{1}{k}})</math> ребрами и легкостью <math>O(k \rho n^{\frac{1}{k}})</math>, где <math>\rho\ </math> = log(Diameter), который можно построить за полиномиальное время.

В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера <math>O(n^{\frac{3}{2}})</math> и 3-остов размера O(n log n). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем выполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время <math>O(n log n + \frac{n}{\epsilon^{d}})</math>. Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.

Остовы исключительно полезны для многих приложений в таких областях, как распределенные системы и коммуникационные сети. В этих приложениях остовы являются основной графовой структурой. Для построения компактных таблиц маршрутизации [16] многие существующие алгоритмы маршрутизации используют ребра разреженного остова для маршрутизации сообщений. В распределенных системах остовы играют важную роль при разработке ''синхронизаторов''. Авербух [3] и Пелег и Ульман [15] показали, что качество остова (выражаемое в терминах коэффициента растяжения и количества ребер остова) тесно связано с временем и коммуникационной сложностью любого синхронизатора сети. Остовы также могут неявно использоваться во множестве алгоритмов для вычисления всех пар аппроксимированных кратчайших путей [5, 9, 18]. Примеры других приложений можно найти в работах [2, 3, 14, 16].

Время выполнения и размер (2k–1)-остова, вычисляемого Алгоритмом II, отличаются в k раз от соответствующих нижних границ для худшего случая. Для любого константного значения k оба эти параметра являются оптимальными. Однако для экстремального значения k, а именно – для k = log n, имеется отклонение с коэффициентом log n. Возможно ли избавиться от этого мультипликативного множителя k ко времени выполнения алгоритма и/или размеру вычисляемого (2k–1)-остова? Представляется, что для решения этой задачи могут быть полезны более тщательный анализ и передовые теоретико-вероятностные инструменты.