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

Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> дуг. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их дуги могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на доминирующих множествах.

1. Формирование кластеров:

Выборка R  V выполняется посредством независимого выбора каждой вершины с вероятностью <math>\frac{1}{\sqrt{n}}</math>. Кластеры будут сформированы вокруг этих выбранных вершин. Вначале кластеры представляют собой {{u}  u  R}. Каждая вершина u  R называется центром своего кластера. Каждая невыбранная вершина v  V – R обрабатывается следующим образом:

(a) Если v не является смежной с какой-либо выбранной вершиной, то каждая дуга, инцидентная v, перемещается в E<math>_{S}</math>.

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