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

Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 69: Строка 69:
Очевидно, что дуга (u, v) была удалена из E’ на этапе 2; предположим, что она была удалена при обработке вершины u. Пусть вершина v входит в кластер с центром x <math>\in</math> R.
Очевидно, что дуга (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>. Следовательно, существует путь ΠUV = u – v’ – x – v между u и v в остове E<math>_{S}</math>, и его вес ограничен weight(Πuv) = 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) с использованием элементарных структур данных и блочной сортировки.
Пусть в начале второго этапа (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].
Алгоритм вычисления (2k–1)-остова исполняет k итераций, причем каждая итерация напоминает первый этап алгоритма нахождения 3-остова. Детали и формальное доказательство можно найти в [6].


Строка 75: Строка 75:


Понятие остова в обобщенном виде исследовалось во многих работах.
Понятие остова в обобщенном виде исследовалось во многих работах.
Аддитивные остовы: описанный выше t-остов аппроксимирует попарные расстояния с мультипликативной ошибкой; его мы будем называть мультипликативным остовом. Аналогичным образом можно определить остов, аппроксимирующий попарные расстояния с аддитивной ошибкой. Такой остов называется аддитивным остовом, а соответствующая ошибка носит название избытка. Эйнгворт и коллеги [1] представили первый аддитивный остов размера O(n3/2 log n) с избытком 2. Босуана и коллеги [7] представили алгоритм построения аддитивного остова размера O(n4/3) с избытком 6. До сих пор остается открытым вопрос, существуют ли более разреженные аддитивные остовы.
 
(α,β)-остов: Элкин и Пелег [11] ввели понятие (α,β)-остова для невзвешенных графов, который можно рассматривать как гибрид мультипликативного и аддитивного остовов. (α,β)-остов представляет собой подграф, такой, что расстояние между любыми двумя вершинами u, v V в этом подграфе ограничено αδ(u, v) + β, где δ(u, v) – расстояние между вершинами u и v в исходном графе. Элкин и Пелег показали, что (1+ε, β)-остов размера O(βn1+δ) для произвольно малых ε, δ > 0 может быть вычислен за счет достаточно большого значения избытка β. Недавно Торуп и Цвик [19] разработали остов с аддитивной ошибкой, сублинейной относительно аппроксимируемого расстояния.
''Аддитивные остовы'': описанный выше t-остов аппроксимирует попарные расстояния с мультипликативной ошибкой; его мы будем называть ''мультипликативным остовом''. Аналогичным образом можно определить остов, аппроксимирующий попарные расстояния с аддитивной ошибкой. Такой остов называется аддитивным остовом, а соответствующая ошибка носит название ''избытка''. Эйнгворт и коллеги [1] представили первый аддитивный остов размера O(n<math>^{3/2 log n}</math>) с избытком 2. Босуана и коллеги [7] представили алгоритм построения аддитивного остова размера O(n<math>^{4/3}</math>) с избытком 6. До сих пор остается открытым вопрос, существуют ли более разреженные аддитивные остовы.
Среди других интересных вариантов остовов – остов с сохранением расстояния, подложенный Боллобасом и коллегами [8], и легковесный остов, предложенный Авербухом и коллегами [4]. Подграф называется d-хранителем, если он сохраняет точные расстояния между каждой парой вершин, разделенных расстоянием не менее d. Легковесный остов стремится минимизировать количество дуг и полный вес дуг. Параметр «легкость» определяется для подграфа как отношение полного веса всех его дуг к весу минимального остовного дерева графа. Авербух и коллеги [4] показали, что для любого взвешенного графа и целого числа k > 1 существует O(k)-остов с O(knl+l/k) дугами и легкостью O(knl/k), где  = log(Diameter), который можно построить за полиномиальное время.
 
 
''(α,β)-остов'': Элкин и Пелег [11] ввели понятие ''(α,β)-остова'' для невзвешенных графов, который можно рассматривать как гибрид мультипликативного и аддитивного остовов. (α,β)-остов представляет собой подграф, такой, что расстояние между любыми двумя вершинами u, v <math>\in</math> V в этом подграфе ограничено αδ(u, v) + β, где δ(u, v) – расстояние между вершинами u и v в исходном графе. Элкин и Пелег показали, что (1+ε, β)-остов размера O(βn<math>^{1+ \delta}</math>) для произвольно малых ε, δ > 0 может быть вычислен за счет достаточно большого значения избытка β. Недавно Торуп и Цвик [19] разработали остов с аддитивной ошибкой, сублинейной относительно аппроксимируемого расстояния.
 
 
Среди других интересных вариантов остовов – ''остов с сохранением расстояния'', предложенный Боллобасом и коллегами [8], и ''легковесный остов'', предложенный Авербухом и коллегами [4]. Подграф называется d-хранителем, если он сохраняет точные расстояния между каждой парой вершин, разделенных расстоянием не менее d. Легковесный остов стремится минимизировать количество дуг и полный вес дуг. Параметр «''легкость''» определяется для подграфа как отношение полного веса всех его дуг к весу минимального остовного дерева графа. Авербух и коллеги [4] показали, что для любого взвешенного графа и целого числа k > 1 существует O(k)-остов с O(knl+l/k) дугами и легкостью O(knl/k), где  = log(Diameter), который можно построить за полиномиальное время.
 
 
В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера O(n3/2) и 3-остов размера O(nlogn). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем исполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время O(n log n + n/εd) . Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.
В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера O(n3/2) и 3-остов размера O(nlogn). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем исполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время O(n log n + n/εd) . Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.


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