Алгоритмы поиска остова во взвешенном графе: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) м (→Алгоритм II) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
== Вычисление 3-остова за линейное время == | == Вычисление 3-остова за линейное время == | ||
Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> | Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> ребер. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их ребра могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на [[доминирующее множество|доминирующих множествах]]. | ||
Вначале имеется множество | Вначале имеется множество ребер E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает ребра E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа. | ||
'''1. Формирование кластеров:''' | '''1. Формирование кластеров:''' | ||
| Строка 42: | Строка 42: | ||
Выборка <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 не является смежной с какой-либо выбранной вершиной, то | (a) Если v не является смежной с какой-либо выбранной вершиной, то каждое ребро, инцидентное v, перемещается в E<math>_{S}</math>. | ||
(b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего к v соседа из числа выбранных вершин ( | (b) Если v является смежной с одной или несколькими выбранными вершинами, примем за N(v, R) ближайшего к v соседа из числа выбранных вершин (связи можно разрывать произвольным образом; однако ради удобства можно считать, что все веса различны.). Ребро (v , N(v, R)) и каждое инцидентное v ребро с весом, меньшим, чем у этой дуги, перемещаются в E<math>_{S}</math>. Затем вершина v добавляется в кластер с центром в N(v, R). | ||
На последнем шагу первого этапа все | На последнем шагу первого этапа все ребра (u, v) из E’, у которых u и v не входят в выборку и принадлежат к разным кластерам, отбрасываются. | ||
Пусть V’ – множество вершин, соответствующих конечным точкам | Пусть V’ – множество вершин, соответствующих конечным точкам ребер E’, оставшимся после завершения первого этапа. Из этого следует, что каждая вершина из V’ является либо вершиной из выборки, либо смежной с одной из таких вершин, и этап 1(b) разбивает V' на непересекающиеся кластеры, в центре каждого из которых находится некоторая вершина из выборки. Заметим, что вследствие последнего этапа каждое ребро в множестве E’ является внутрикластерным ребром. Граф (V’, E’) т соответствующее разбиение V’ на кластеры передается на вход следующего (второго) этапа. | ||
'''2. Соединение вершин с соседними кластерами:''' | '''2. Соединение вершин с соседними кластерами:''' | ||