4501
правка
Алгоритмы поиска остова во взвешенном графе: различия между версиями
Перейти к навигации
Перейти к поиску
м
Алгоритмы поиска остова во взвешенном графе (посмотреть исходный код)
Версия от 00:19, 19 февраля 2012
, 19 февраля 2012→Вычисление 3-остова за линейное время
Irina (обсуждение | вклад) м (→Алгоритм I) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
== Вычисление 3-остова за линейное время == | == Вычисление 3-остова за линейное время == | ||
Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> дуг. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их дуги могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на | Чтобы удовлетворять ограничениям 3-остова, вершина должна внести в остов вклад в размере в среднем <math>\sqrt{n}</math> дуг. Таким образом, вершины степени <math>O(\sqrt{n})</math> обработать легко, поскольку все их дуги могут быть выбраны для остова. Для вершин более высокой степени применяется схема кластеризации (группировки), основанная на [[доминирующие множества|доминирующих множествах]]. | ||
Вначале имеется множество дуг E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает дуги E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа. | Вначале имеется множество дуг E’, инициализированное равным E, и пустой остов E<math>_{S}</math>. Алгоритм просматривает дуги E’, переносит некоторые из них в остов E<math>_{S}</math> и отбрасывает остальные. Это происходит в два этапа. | ||