graph-theory - Minumum Spanning Tree

Question

I have a homework about graph and minimum spanning tree

Suppose for a given graph G1, we have computed a minimum spanning tree T1. Now ,a new edge to G1 is added.We call this new graph with the added edge G2. Describe an algorithm to compute the minimum spanning tree T2 OF G2 efficiently by jut adjusting T1.

Answer 1

その新しいエッジ、たとえば e' を T1 に追加してみてください。これにより、T1 にサイクルが形成されます。問題は、T1 + e' の一意のサイクルで最大の重み付きエッジを見つけることになりました。

前の手順で見つけたエッジを T1 + e' から削除すると、T2 が得られます。