Удалить узел из MST: повторно подключиться к Kruskal

У меня есть MST и мне нужно удалить узел. Я знаю, что для этого есть алгоритм в O(log^4(n)), но поскольку MST содержит менее 50 узлов и 2500 ребер, а ребра уже отсортированы, я хотел найти более простое решение: я создаю union для каждого подключенного компонента и запустите Kruskal для их повторного подключения.

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

Однако я не нашел ничего, что подтверждало бы, что это работает, поэтому я хотел перепроверить здесь:

Является ли результирующее дерево минимальным остовным деревом среди оставшихся узлов и ребер?


graph algorithm graph-algorithm kruskals-algorithm
person Ferdi K    schedule 15.05.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Он работает нормально, но не так быстро, как O(log^4(n))

Доказательство того, что это работает, простое: используя алгоритм Крускала, ребро выбирается тогда и только тогда, когда его конечные точки не связаны каким-либо путем только через более дешевые/более ранние ребра.

Удаление вершины и ее ребер не создает новых путей (а только удаляет пути), поэтому любое ранее выбранное ребро все равно будет выбрано, если вы снова запустите весь алгоритм.

person Matt Timmermans    schedule 15.05.2020