4551
правка
Полностью динамические минимальные остовные деревья: различия между версиями
Материал из WEGA
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 12:25, 19 июля 2014
, 19 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
== Основные результаты == | == Основные результаты == | ||
Алгоритм поддержки динамического минимального остовного леса основан на алгоритме динамической связности, приведенном в статье | Алгоритм поддержки динамического минимального остовного леса основан на алгоритме динамической связности, приведенном в статье «[[Полностью динамическая связность]]». После нескольких небольших модификаций алгоритм позволяет поддерживать минимальный остовный лес взвешенного неориентированного графа в присутствии исключительно операций удаления ребер [13]. Затем может быть применена редукция из [11], позволяющая сделать алгоритм с удалением ребер полностью динамическим. | ||
Вначале опишем декрементный алгоритм, поддерживающий минимальный остовный лес в присутствии исключительно операций удаления ребер. На протяжении последовательности операций удаления алгоритм поддерживает остовный лес F на динамически меняющемся графе G. Ребра, принадлежащие F, называются древесными ребрами; остальные ребра (из G – F) называются недревесными ребрами. Пусть e – удаляемое ребро. Если ребро e является недревесным, то минимальный остовный лес не меняется. Остается рассмотреть случай, когда ребро e является древесным ребром леса F. Пусть T – дерево леса F, содержащее e. В этом случае удаление ребра e разбивает дерево T на два поддерева – T1 и T2. Для обновления минимального остовного леса необходимо найти ребро с минимальным весом, одна конечная точка которого принадлежит дереву T1, а другая - дереву T2. Такое ребро называется ребром замены для e. | Вначале опишем декрементный алгоритм, поддерживающий минимальный остовный лес в присутствии исключительно операций удаления ребер. На протяжении последовательности операций удаления алгоритм поддерживает остовный лес F на динамически меняющемся графе G. Ребра, принадлежащие F, называются древесными ребрами; остальные ребра (из G – F) называются недревесными ребрами. Пусть e – удаляемое ребро. Если ребро e является недревесным, то минимальный остовный лес не меняется. Остается рассмотреть случай, когда ребро e является древесным ребром леса F. Пусть T – дерево леса F, содержащее e. В этом случае удаление ребра e разбивает дерево T на два поддерева – T1 и T2. Для обновления минимального остовного леса необходимо найти ребро с минимальным весом, одна конечная точка которого принадлежит дереву T1, а другая - дереву T2. Такое ребро называется ребром замены для e. | ||
