4551
правка
Полностью динамические минимальные остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 12:26, 19 июля 2014
, 19 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Алгоритм поддержки динамического минимального остовного леса основан на алгоритме динамической связности, приведенном в статье «[[Полностью динамическая связность]]». После нескольких небольших модификаций алгоритм позволяет поддерживать минимальный остовный лес взвешенного неориентированного графа в присутствии исключительно операций удаления ребер [13]. Затем может быть применена редукция из [11], позволяющая сделать алгоритм с удалением ребер полностью динамическим. | Алгоритм поддержки динамического минимального остовного леса основан на алгоритме динамической связности, приведенном в статье «[[Полностью динамическая связность]]». После нескольких небольших модификаций алгоритм позволяет поддерживать минимальный остовный лес взвешенного неориентированного графа в присутствии исключительно операций удаления ребер [13]. Затем может быть применена редукция из [11], позволяющая сделать алгоритм с удалением ребер полностью динамическим. | ||
Вначале опишем декрементный алгоритм, поддерживающий минимальный остовный лес в присутствии исключительно операций удаления ребер. На протяжении последовательности операций удаления алгоритм поддерживает остовный лес F на динамически меняющемся графе G. Ребра, принадлежащие F, называются древесными ребрами; остальные ребра (из G – F) называются недревесными ребрами. Пусть e – удаляемое ребро. Если ребро e является недревесным, то минимальный остовный лес не меняется. Остается рассмотреть случай, когда ребро e является древесным ребром леса F. Пусть T – дерево леса F, содержащее e. В этом случае удаление ребра e разбивает дерево T на два поддерева – | Вначале опишем декрементный алгоритм, поддерживающий минимальный остовный лес в присутствии исключительно операций удаления ребер. На протяжении последовательности операций удаления алгоритм поддерживает остовный лес F на динамически меняющемся графе G. Ребра, принадлежащие F, называются [[древесные ребра|древесными ребрами]]; остальные ребра (из G – F) называются [[недревесные ребра|недревесными ребрами]]. Пусть e – удаляемое ребро. Если ребро e является недревесным, то минимальный остовный лес не меняется. Остается рассмотреть случай, когда ребро e является древесным ребром леса F. Пусть T – дерево леса F, содержащее e. В этом случае удаление ребра e разбивает дерево T на два поддерева – <math>T_1</math> и <math>T_2</math>. Для обновления минимального остовного леса необходимо найти ребро с минимальным весом, одна конечная точка которого принадлежит дереву <math>T_1</math>, а другая - дереву <math>T_2</math>. Такое ребро называется [[ребро замены|ребром замены]] для e. | ||
Для выполнения поиска ребер замены алгоритм динамической связности присваивает каждому ребру e уровень <math>\ell (e) \; </math> и на основе этих уровней поддерживает множество под-лесов минимального остовного дерева F: для каждого уровня i лес <math>F_i \; </math> является под-лесом, порожденным древесными ребрами уровня выше ''или равного'' i. Обозначив за L максимальный уровень ребра, получаем следующее: | Для выполнения поиска ребер замены алгоритм динамической связности присваивает каждому ребру e уровень <math>\ell (e) \; </math> и на основе этих уровней поддерживает множество под-лесов минимального остовного дерева F: для каждого уровня i лес <math>F_i \; </math> является под-лесом, порожденным древесными ребрами уровня выше ''или равного'' i. Обозначив за L максимальный уровень ребра, получаем следующее: | ||