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

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

Пусть 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>. Из элементарной вероятности следует, что для каждой вершины <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>, следовательно, ожидаемое количество дуг, добавленных к остову на второй фазе, составляет не более n<math>^{3/2}</math>. Следовательно, ожидаемый размер остова E<math>_{S}</math> по окончании работы Алгоритма II в вышеописанном виде не превосходит 2n<math>^{3/2}</math>. Алгоритм выполняется повторно, если размер остова превосходит 3n<math>^{3/2}</math>. Из неравенства Маркова следует, что ожидаемое количество таких повторений будет составлять O(1).

Установим теперь, что E<math>_{S}</math> является 3-остовом. Заметим, что для каждой дуги edge (u, v) <math>\notin</math> E<math>_{S}</math>, вершины u и v на первом этапе принадлежат к одному кластеру. Теперь имеет место один из двух случаев.

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

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