2
$\begingroup$

Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$ Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$.

I'm using a common algorithm to update $T$ so we don't have to find a mst of $G_2$ from scratch. The algorithm is to first take out $e$ from $T$, which will result in two subtrees $T_a$, which contains $a$, and $T_b$ which contains $b$. Then, I iterate over all the edges in $G_2$ and find the edge with the minimum weight that has one ed in $T_a$ and the other end in $T_b$. Call this edge $e_2$. Then I add this edge into $T$ to get $T_2$.

I'm having a lot of difficulty proving that $T_2$ is a mst for $G_2$. I've proved that $T_2$ is a spanning tree of $G_2$, but again, I'm having a lot of difficulty with proving that $T_2$ is a minimum spanning tree.

Any help would be greatly appreciated!

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

Let $S$ be a spanning tree of an edge-weighted graph. We call $S$ a local-minimum spanning tree (local-MST) of the graph if every edge not in $S$ weighs the heaviest in the cycle created when that edge is added to $S$.

Here is a very useful characterization of MST.

A spanning tree is an MST if and only if it is a local-MST.

Proofs of the above theorem can be found here or here.

Once we are armed with above theorem, it is easy to prove the algorithm in the question does produce an MST.

Proof of the algorithm: $G$ and $G_2$ will be referred as $(G, w_1)$ and $(G, w_2)$ respectively, where $w_1$ is the the original weight function and and $w_2$ is the updated weight function. $w_1$ and $w_2$ are the same except on $e$.

Let $G_a$ be the subgraph spanned by $T_a$ and $G_b$ be the subgraph spanned by $T_b$. Every vertex of $G$ is either in $G_a$ or in $G_b$.

Consider an arbitrary edge $f$ of $G$. Let $\mathcal C$ be the cycle created when we add $f$ to $T_2$.

  • If $f$ is in $G_a$ or $G_b$, then $e$ is not part of $\mathcal C$. So $\mathcal C$ is also the cycle created when we add $f$ to $T$. Since $T$ is an MST of $(G, w_1)$, $f$ weighs the heaviest in that cycle with respect to $w_1$ and, hence, with respect to $w_2$ as well.

  • Otherwise, $f$ connects one vertex in $G_a$ and one vertex in $G_b$. $\mathcal C$, as a cycle, must include $e_2$ since $e_2$ is the only edge in $T_2$ that connect $G_a$ and $G_b$.

    enter image description here

    In the above illustration, all green edges together with $e$ is the cycle created when $e_2$ is added to $T$. All blue edges together with $e$ is the cycle created when $f$ is added to $T$. All green and blue edges together is $\mathcal C$.

    Since $T$ is a local-MST w.r.t $w_1$, $e_2$ weighs the heaviest on the green cycle w.r.t. $w_1$. Since $w_2$ and $w_1$ agrees except on $e$, $$w_2(e_2)\ge w_2(\text{every green edge}).$$

    Similarlyly we have
    $$w_2(f)\ge w_2(\text{every blue edge}).$$

    Since $w_2(f)\ge w_2(e_2)$ by the specification of the algorithm, $f$ weighs the heaviest among all green edges and all green edges. That is, $f$ weighs the heaviest in $\mathcal C$ w.r.t. $w_2$.

    There are configurations other than the illustration. For example, $e_2$ or $f$ might be the same as $e$. The green cycle and the blue cycle might have multiple overlapping segments. In every case, similar argument with the same inequalities shows that $f$ weighs the heaviest in $\mathcal C$ w.r.t. $w_2$.

So we have shown that $T_2$ is a local-MST of $(G, w_2)$. By the above theorem, $T_2$ is an MST of $(G, w_2)$.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ This answer does not use the fact that the weight of that edge in the MST is increased. That is, the same algorithm is still correct if the weight is decreased. $\endgroup$
    – John L.
    Commented Apr 19, 2020 at 23:08
  • 1
    $\begingroup$ Another proof could be applying Kruskal's algorithm. Every MST can be obtained by Kruskal. Suppose we can construct $T$ w.r.t to $w_1$ by adding $e_1$, $e_2$, $\cdots$, $e_i=e$, $\cdots$, $e_{n-1}$ successively for some $i$ according to Kruskal's algorithm. Let $k$ be the largest index such that $w_1(e_k)\le w_2(f)$. Drop $e$ from the sequence. Insert $f$ right after $e_k$. Verify the new sequence can be obtained by Kruskal w.r.t to $w_2$. (We can use Prim's algorithm, too.) $\endgroup$
    – John L.
    Commented Apr 23, 2020 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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