4430
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 20:56, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [11]: алгоритм, разработанный Холмом, де Лихтенбергом и Торупом, отвечает на вопрос о связности за время <math>O(log \; n/log \; log \; n)</math> в наихудшем случае и поддерживает вставку и удаление дуг за амортизированное время <math>O(log^2 n \; )</math>. | Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [11]: алгоритм, разработанный Холмом, де Лихтенбергом и Торупом, отвечает на вопрос о связности за время <math>O(log \; n/log \; log \; n)</math> в наихудшем случае и поддерживает вставку и удаление дуг за амортизированное время <math>O(log^2 n \; )</math>. | ||
Алгоритм поддерживает [[остовный лес]] F на динамически меняющемся графе G. Дуги в F называются [[древесная дуга|древесными дугами]]. Пусть e – древесная дуга леса F; пусть T – дерево из F, содержащее эту дугу. При удалении дуги e деревья | Алгоритм поддерживает [[остовный лес]] F на динамически меняющемся графе G. Дуги в F называются [[древесная дуга|древесными дугами]]. Пусть e – древесная дуга леса F; пусть T – дерево из F, содержащее эту дугу. При удалении дуги e деревья <math>T_1</math> и <math>T_2</math>, полученные из T в результате удаления e, могут быть связаны вновь в том и только том случае, если существует недревесная дуга в G, одна конечная точка которой располагается в <math>T_1</math>, а другая – в <math>T_2</math>. Такая дуга называется дугой замены для e. Иными словами, если имеется дуга замены для e, T восстанавливает связность при помощи этой дуги замены; в противном случае удаление e создает новую компоненту связности в графе G. | ||