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

Выборка <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> обрабатывается следующим образом:

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

2. Соединение вершин с соседними кластерами:

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