4
$\begingroup$

Let $\textit{G(V,E)}$ be an undirected connected graph with distinct costs on its edges. Initialize $\textit{T}$ to be any spanning tree of $\textit{G}$. Consider an algorithm which replaces an edge $\textit{e}$ in $\textit{T}$ by an edge $\textit{e'}$ not in $\textit{T}$, if $\textit{e' < e}$ and replacing it still maintains $\textit{T}$ to be a spanning tree.

I want to prove that this algorithm results in a minimum cost spanning tree of $\textit{G}$.

I am trying to prove this by contradiction - consider that $ \textit{T}$ is the tree which we obtain when the algorithm ends. We assume that there exists $\textit{T'}$ such that $\textit{W(T') < W(T)}$.

Attempt: I tried considering an edge $\textit{e}$ to be the lowest cost edge which is in $\textit{T'}$ but not in $\textit{T}$ (there is at least one since both are different spanning trees). We add $\textit{e}$ to $\textit{T}$ - thus, creating a cycle (since $\textit{T}$ was a spanning tree). There are two possible cases:

  1. $\textit{e}$ is smaller than all the edges of the cycle it induced. But, in this case, the algorithm would not have stopped at $\textit{T}$, it would have replaced one of the edges of the cycle by $\textit{e}$.

  2. $\textit{e}$ is larger than all the edges of the cycle it induced. I suppose this should contradict the minimality of $\textit{T'}$.

Am I anywhere on the right track? I don't know if considering the cycle is the way to do this.

$\endgroup$
  • 1
    $\begingroup$ Must I be either shorter than all my friends, or taller than all my friends? $\endgroup$ – j_random_hacker Mar 6 '18 at 15:36
  • $\begingroup$ We're given distinct edges $\endgroup$ – Mallika Mar 6 '18 at 22:31
  • $\begingroup$ My friends and I all have different heights. My question stands. $\endgroup$ – j_random_hacker Mar 7 '18 at 1:02
  • $\begingroup$ Ah, completely missed it! Okay, I need to think more about this $\endgroup$ – Mallika Mar 7 '18 at 14:16
  • $\begingroup$ Did you manage to get further? You're pretty close already :) One small thing: You mention "minimality of $T'$" towards the end, but earlier you do not explicitly say that $T'$ is minimal, only that $W(T') < W(T)$. $\endgroup$ – j_random_hacker Mar 8 '18 at 17:40
1
$\begingroup$

It is not immediate to see whether OP’s approach can be adapted easily to a full proof.

Here is an answer to the same question but phrased differently, a local minimum in the graph of spanning trees is a (global) minimum spanning tree.

I will present another proof, which is more flexible and probably easier to understand.

Let $G$ be an undirected connected (finite) graph with distinct costs on its edges, as in the original question. Consider the delete-heaviest-edge algorithm on $G$, which removes the heaviest edge in a cycle until no cycle remains. Just to be clearer, let me call the remaining edges at the end of the algorithm $H$. Let us show that $H$ is the minimum cost spanning tree (MST) of $G$.

$H$ is a spanning tree of $G$ because of the following.

  • $H$ is connected, since $G$ is connected and all we have done is breaking cycles.
  • $H$ is has no cycle since the algorithm ends only if there is no cycle.
  • $H$ has all vertices of $G$ since no vertex of $G$ has ever been deleted.

Because of the the cycle property, any edge in any minimal cost spanning tree (MST) of $G$ is never deleted. So all edges of any MST of $G$ remain in $H$. However, any spanning tree of $G$ has the same number of edges, so $H$ must be the unique MST of $G$. (Yes, we have also proved that there is only one MST of $G$, thanks to the distinctness of the costs).

So we have proved that the delete-heaviest-edge algorithm finds the MST. The flexibility of that algorithm is that in each step we can choose any particular cycle.

Following the OP, let $T$ be the spanning tree which we obtain at the end of OP's algorithm. Initialize $G'$ to be a copy of $G$ and $T'$ is the spanning tree of $G'$ that corresponds to $T$. Let $e'$ be an edge in $G'$ but not in $T'$. If we add $e'$ to $T'$, we will create a cycle since $T'$ is spanning. Note that $e'$ must be the unique heaviest edge in that cycle; otherwise, we can substitute $e'$ for that unique heaviest edge, which is in $T'$, to get a lighter spanning tree, which means the OP's algorithm must not end with $T$, a contradiction. Let us run the delete-heaviest-edge algorithm on $G'$ in the following way. We choose that cycle and delete $e'$ from $G'$. Repeat until all edges in $G'$ but not in $T'$ are deleted. What remains is exactly $T'$. Since $T'$ has no cycle, we have actually run the delete-heaviest-edge algorithm to the end. As we have proved, $T'$ is the MST of $G'$. That is, $T$ is the MST of $G$.

$\endgroup$
  • $\begingroup$ The "delete-heaviest-edge algorithm" in my answer is Vyssotsky’s algorithm according to the book, Algorithms by Robert Sedgewick and Kevin Wayne, fourth edition. $\endgroup$ – Apass.Jack Jul 30 '18 at 17:59

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.