1つのノードが消えたときにMSTを構成する方法は？

Question

私は研究をしており、質問に固執しています：

私は最小限のスパニングツリー（プリムアルゴリズム）を使用しています。ツリーの1つのノードが削除されるようになりました。最適性がまだ維持されるように私の木を整理しますか？

私はいくつかの提案をここで探しており、私はあなたの助けに感謝します。

ありがとうございました！

Answer 1

削除された頂点がMSTの葉であった場合は、何もする必要はありません。まだスパニングツリーがあり、最適な状態です。

葉でない場合は、2つのサブツリーがあります。あなたがする必要があるのは、2つのサブツリーの間に存在する最短エッジでそれらを再接続するだけです。そのエッジを見つける最良の方法はおそらく、プリムのアルゴリズム（あるいは、すべての頂点のペアを考慮することによって、O（n^2）において）で使用したデータ構造を使用することです。

Answer 2

ツリー内のノードを削除すると、グラフが複数の切断されたコンポーネントに分割されることがあります。最悪の場合、すべてのエッジが1つのセントラルノードからスターのように他のすべてのセントラルノードに移動するMSTを想像してください。この場合、中央ノードが削除された場合、MST全体を再実行する必要があります。だから、私は短い答えがあると思う - それはどのノードが削除されるかによって決まります。解決策は、上記のように行うことです - 削除されたノードのために切断されているすべてのコンポーネントを見つけ、それらを貪欲に接続します。これは、0（葉ノードが除去されている場合）からn-1（星の中心が除去された場合）から伸びる可能性があります。

Answer 3

この問題は十分に研究されています。 2001年に行われた調査では、グラフのデータ構造を維持して、エッジを挿入または削除し、最小限のスパニングツリーを時間O（ログ n）に更新できるようになりました。結ばれた誰もこれまでに思い付くことができました。このアルゴリズムを記述した論文は、緻密かつトリッキーですが、もし興味があるなら、あなたはそれをここに見つけることができます：

Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity

は、この情報がお役に立てば幸い！