4501
правка
Алгоритмы поиска остова во взвешенном графе: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмы поиска остова во взвешенном графе (посмотреть исходный код)
Версия от 01:20, 18 декабря 2011
, 18 декабря 2011нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 42: | Строка 42: | ||
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> обрабатывается следующим образом: | ||
(a) Если v не является смежной с какой-либо выбранной вершиной, то каждая дуга, инцидентная v, перемещается в E<math>_{S}</math>. | (a) Если v не является смежной с какой-либо выбранной вершиной, то каждая дуга, инцидентная v, перемещается в E<math>_{S}</math>. | ||
(b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего | (b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего к v соседа из числа выбранных вершин (Связи можно разрывать произвольным образом; однако ради удобства можно считать, что все веса различны.). Дуга (v , N(v, R)) и каждая инцидентная v дуга с весом, меньшим, чем у этой дуги, перемещаются в E<math>_{S}</math>. Затем вершина v добавляется в кластер с центром в N(v, R). | ||
На последнем шагу первого этапа все дуги (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются. | На последнем шагу первого этапа все дуги (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются. | ||
Пусть 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 формируется путем случайного и независимого выбора каждой вершины с вероятностью 1/ | Количество дуг, добавленных к остову E<math>_{S}</math> за время исполнения описанных этапов алгоритма, можно ограничить следующим образом. Заметим, что множество выборки R формируется путем случайного и независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Из элементарной вероятности следует, что для каждой вершины v V ожидаемое количество инцидентных ей дуг с весами меньше, чем у (v, N (v, R)), не превосходит n. Таким образом, ожидаемое количество дуг, вносимых в остов каждой вершиной на первом этапе алгоритма, не превосходит <math>\sqrt{n}</math>. Количество дуг, добавленных к остову на второй фазе, составляет O(nR). Поскольку ожидаемый размер выборки R равен n, следовательно, ожидаемое количество дуг, добавленных к остову на второй фазе, составляет не более 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 на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев. | ||