4501
правка
Алгоритмы поиска остова во взвешенном графе: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмы поиска остова во взвешенном графе (посмотреть исходный код)
Версия от 01:24, 18 декабря 2011
, 18 декабря 2011нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 40: | Строка 40: | ||
Вначале имеется множество дуг E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает дуги E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа. | Вначале имеется множество дуг E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает дуги E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа. | ||
1. Формирование кластеров: | '''1. Формирование кластеров:''' | ||
Выборка <math>R \subset V</math> выполняется посредством независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Кластеры будут сформированы вокруг этих выбранных вершин. Вначале кластеры представляют собой {{u}<math>\mid</math>u <math>\in </math>R}. Каждая вершина <math>u \in R</math> называется центром своего кластера. Каждая невыбранная вершина <math>v \in V - R</math> обрабатывается следующим образом: | Выборка <math>R \subset V</math> выполняется посредством независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Кластеры будут сформированы вокруг этих выбранных вершин. Вначале кластеры представляют собой {{u}<math>\mid</math>u <math>\in </math>R}. Каждая вершина <math>u \in R</math> называется центром своего кластера. Каждая невыбранная вершина <math>v \in V - R</math> обрабатывается следующим образом: | ||
| Строка 51: | Строка 51: | ||
Пусть V’ – множество вершин, соответствующих конечным точкам дуг E’, оставшимся после завершения первого этапа. Из этого следует, что каждая вершина из V’ является либо вершиной из выборки, либо смежной с одной из таких вершин, и этап 1(b) разбивает V' на непересекающиеся кластеры, в центре каждого из которых находится некоторая вершина из выборки. Заметим, что вследствие последнего этапа каждая дуга в множестве E’ является внутрикластерной дугой. Граф (V’, E’) т соответствующее разбиение V’ на кластеры передается на вход следующего (второго) этапа. | Пусть V’ – множество вершин, соответствующих конечным точкам дуг E’, оставшимся после завершения первого этапа. Из этого следует, что каждая вершина из V’ является либо вершиной из выборки, либо смежной с одной из таких вершин, и этап 1(b) разбивает V' на непересекающиеся кластеры, в центре каждого из которых находится некоторая вершина из выборки. Заметим, что вследствие последнего этапа каждая дуга в множестве E’ является внутрикластерной дугой. Граф (V’, E’) т соответствующее разбиение V’ на кластеры передается на вход следующего (второго) этапа. | ||
2. Соединение вершин с соседними кластерами: | '''2. Соединение вершин с соседними кластерами:''' | ||
Каждая вершина v графа (V’, E’) обрабатывается следующим образом. | Каждая вершина v графа (V’, E’) обрабатывается следующим образом. | ||
Пусть E’(v, c) – дуги из множества E’, инцидентные v, из кластера c. Для каждого кластера c, являющегося соседом v, дуга из E’(v, c) с наименьшим весом перемещается в E<math>_{S}</math>; остальные дуги отбрасываются. | Пусть 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>. Из элементарной вероятности следует, что для каждой вершины v | Количество дуг, добавленных к остову 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>, следовательно, ожидаемое количество дуг, добавленных к остову на второй фазе, составляет не более n3/2. Следовательно, ожидаемый размер остова E<math>_{S}</math> по окончании работы Алгоритма II в вышеописанном виде не превосходит 2n3/2. Алгоритм выполняется повторно, если размер остова превосходит 3n3/2. Из неравенства Маркова следует, что ожидаемое количество таких повторений будет составлять O(1). | ||
Установим теперь, что E<math>_{S}</math> является 3-остовом. Заметим, что для каждой дуги edge (u, v) E<math>_{S}</math>, вершины u и v на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев. | Установим теперь, что E<math>_{S}</math> является 3-остовом. Заметим, что для каждой дуги edge (u, v) E<math>_{S}</math>, вершины u и v на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев. | ||