4817
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 13:54, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
== Основные результаты == | == Основные результаты == | ||
Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [ ]: алгоритм, разработанный Холмом, де Лихтенбергом и Торупом, отвечает на вопрос о связности за время O(log n/log log n) в наихудшем случае и поддерживает вставку и удаление дуг за амортизированное время O( | Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [11]: алгоритм, разработанный Холмом, де Лихтенбергом и Торупом, отвечает на вопрос о связности за время <math>O(log \; n/log \; log \; n)</math> в наихудшем случае и поддерживает вставку и удаление дуг за амортизированное время <math>O(log^2 n \; )</math>. | ||
Алгоритм поддерживает остовный лес F на динамически меняющемся графе G. Дуги в F называются древесными дугами. Пусть e – древесная дуга леса F; пусть T – дерево из F, содержащее эту дугу. При удалении дуги e деревья T1 и T2, полученные из T в результате удаления e, могут быть связаны вновь в том и только том случае, если существует недревесная дуга в G, одна конечная точка которой располагается в T1, а другая – в T2. Такая дуга называется дугой замены для e. Иными словами, если имеется дуга замены для e, T восстанавливает связность при помощи этой дуги замены; в противном случае удаление e создает новую компоненту связности в графе G. | |||
Алгоритм поддерживает [[остовный лес]] F на динамически меняющемся графе G. Дуги в F называются [[древесная дуга|древесными дугами]]. Пусть e – древесная дуга леса F; пусть T – дерево из F, содержащее эту дугу. При удалении дуги e деревья T1 и T2, полученные из T в результате удаления e, могут быть связаны вновь в том и только том случае, если существует недревесная дуга в G, одна конечная точка которой располагается в T1, а другая – в T2. Такая дуга называется дугой замены для e. Иными словами, если имеется дуга замены для e, T восстанавливает связность при помощи этой дуги замены; в противном случае удаление e создает новую компоненту связности в графе G. | |||
| Строка 66: | Строка 67: | ||
Для модели битового зонда наилучшая верхняя граница на одну операцию достигается при использовании алгоритма теоремы 2; она составляет O(log2 n/ log log log n). Следовательно, разрыв между верхней и нижней границами ограничен дважды логарифмическим множителем. | Для модели битового зонда наилучшая верхняя граница на одну операцию достигается при использовании алгоритма теоремы 2; она составляет O(log2 n/ log log log n). Следовательно, разрыв между верхней и нижней границами ограничен дважды логарифмическим множителем. | ||
== Применение == | == Применение == | ||
