1
$\begingroup$

The problem is as follows:

Given an edge and a graph, calculate the weight of MST over all spanning trees that contains the given edge. The MST can be found by running Prim's algorithm starting with this edge included. But this query is asked for multiple edges for the same graph so a more efficient algorithm is required (each of them is calculated independently).

The solution for this problem is to first find a MST for the graph and for each given edge calculate the maximum weight of the edges in the cycle that results from adding this edge. the result would be new weight = old weight + d(u, v) - max weight. What is the proof of correctness for this algorithm?

$\endgroup$
0
$\begingroup$

Assume the algorithm works for graphs with $n-1$ vertices. Let $|G| = n$. Let $T$ be any MST found by Prim's algorithm. Remove a vertex $v$ from $G$ that is not adjacent to $e$, which is a leaf of $T$, of maximal weight. The restriction of $T$ is still an MST, and the modification according to your algorithm is by induction an MST among those containing $e$. Re-adjoin $v$. By correctness of the one-edge algo, the modified $T$ is an MST.

$\endgroup$

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.