Как организовать MST, когда один узел исчезнет?

Question

Я занимаюсь исследованиями и застрял с вопросом:

У меня минимальное остовное дерево (алгоритм prim), теперь один узел в моем дереве удаляется.Можно ли реорганизовать мое дерево так, чтобы оптимальность сохранялась?

Я ищу несколько предложений здесь и буду признателен за вашу помощь.

Спасибо!

Answer 1

Эта проблема хорошо изучена. Исследования, проведенные в 2001 году, позволили сохранить структуру графических данных, чтобы вы могли вставлять или удалять ребра и обновлять минимальное остовное дерево за время O (log ⁴ n), что, насколько мне известно лучшее время, которое кто-либо смог придумать до сих пор. Документ, описывающий этот алгоритм, является плотным и хитрым, но если вам интересно, вы можете найти его здесь:

Полилогарифмические детерминированные полностью динамические алгоритмы для связности, минимального остовного дерева, 2-ребра и двусвязности

Надеюсь, это поможет!

Answer 2

Когда вы удаляете узел в дереве, он может разделить график на более чем один отключенный компонент.В худшем случае, представьте себе MST, где все ребра проходят от одного центрального узла ко всем остальным - как звезда.В этом случае, если центральный узел удален, весь MST должен быть переделан.Итак, я думаю, что короткий ответ - это зависит от того, какой узел удаляется.Решение состоит в том, чтобы сделать это, как указано выше, - найти все компоненты, которые были отключены из-за удаленного узла, и жадно подключить их.Это может растянуться от 0 (если удален листовой узел) до n-1 (если удален центр звезды)

Answer 3

Если удаленная вершина была листом MST, вам не нужно ничего делать: у вас все еще есть связующее дерево, и оно все еще оптимально.

Если это не был лист, вы теперьесть два поддерева.Все, что вам нужно сделать, это восстановить их с помощью кратчайшего ребра, которое существует между двумя поддеревьями.Вероятно, лучший способ найти это ребро - использовать любую структуру данных, которую вы использовали для алгоритма Прима (или, как правило, в O (n ^ 2), учитывая все пары вершин).