Let $G(V,E)$ an undirected and connected graph with the weight function $w:E\to \mathbb{R}$. We are given $T$, an MST of $G$. Now we remove $e_1,e_2,e_3$ from $G$ (which also appear in $T$) and get a new graph, $G'$. Describe an efficient algorithm to find an MST of $G'$.

My intuition tells me that we can throw those $3$ edges and run Prim algorithm for $G'$ starting from $T-\{e_1,e_2,e_3\}$.

Is my intuition correct? Could help me formulate this?


Assume that you remove the edges one after the other. After removing $e_1$ your tree falls into two connected components. Running one iteration of Prim's Algorithm on one of these components adds an edge of minimum weight connecting both components. The resulting subgraph is again a tree.

A MST is a tree graph $T$ such that if we remove an edge $e$ from $T$ then $e$ is a minimum cost edge of the resulting cut.

Since the new subgraph is a tree fulfilling this property, we found a MST for the new graph. This procedure can be used for $e_2$ and $e_3$ as well which shows that your approach (throw away all three edges together) works as well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.