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

Количество дуг, добавленных к остову 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).

Случай 1: (u и v принадлежат к одному кластеру)

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

Случай 2: (u и v принадлежат к разным кластерам)

Пусть в начале второго этапа (u, v’)  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) с использованием элементарных структур данных и блочной сортировки.