4551
правка
Полностью динамические минимальные остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
м
Полностью динамические минимальные остовные деревья (посмотреть исходный код)
Версия от 12:21, 19 июля 2014
, 19 июля 2014→Постановка задачи
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Пусть G = (V, E) – неориентированный взвешенный граф. Рассматривается задача эффективной поддержки информации о минимальном остовном дереве графа G (либо минимальном остовном лесе, если G не является связным), подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен выполнять операции обновления быстрее, чем вычислять полное минимальное остовное дерево с нуля. | Пусть G = (V, E) – неориентированный взвешенный граф. Рассматривается задача эффективной поддержки информации о минимальном остовном дереве графа G (либо минимальном остовном лесе, если G не является связным), подверженного динамическим изменениям – таким как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен выполнять операции обновления быстрее, чем вычислять полное минимальное остовное дерево с нуля. | ||
Алгоритм называется полностью динамическим, если он поддерживает как вставку ребер, так и удаление ребер. Частично динамический алгоритм поддерживает либо вставку, либо удаление ребер; инкрементный алгоритм поддерживает только вставку ребер, декрементный – только удаление. | Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку ребер, так и удаление ребер. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление ребер; [[инкрементный алгоритм]] поддерживает только вставку ребер, [[декрементный алгоритм|декрементный]] – только удаление. | ||
== Основные результаты == | == Основные результаты == | ||