2
$\begingroup$

I have to prove that the following algorithm finds the minimal spanning tree. Let $G$ be the graph were doing the procedure on, and all edges have different weights.

Step 1: Sort the edges in descending order of their weights, meaning : $c(e_1)>c(e_2)>c(e_3)...>c(e_n)$.

Step 2: For $i=1$ to $n$ If $T-{e_i}$ is connected, then $T=T-{e_i}$

As I understand at first have to prove that after the procedure the result is in fact a tree. This is easy, because we obviously get a connected graph and without a cycle at that (because we erase the reduntant edges), then what we get is a tree.

But how to prove that it is in fact optimal? I tried something along these lines.

Let's assume to the contrary that the tree $T$ we get is not optimal, and some other tree $T'$ is.

Let's analyze all these edges one by one. In the begining all the edges of $T'$ are in $G$. We then erase edges from this graph one by one using the algorithm. Let $e_i$ be the first edge that's kept in $G$ and is not in $T'$ or vice versa. Let $e_i$ be this element. If $e_i$ is this element and it's in $T'$ but not $G$ then obviously the sum of the first $i$ element in descending order in $T'$ is bigger than in $G$. Now I would like to show, that if $e_i$ is in $G$ but not in $T'$ then we ran into some kind of problem, but I have a problem with that. If we erased $e_i$ from $G$ then we would disconnect the graph. But would $T'$ without $e_i$ too be disconnected? It'd be nice if it were obviously, because then my thesis would be proven outright.

$\endgroup$

1 Answer 1

3
$\begingroup$

Let $i$ be minimal with $T$ and $T'$ disagreeing on $e_i$. So $e_1, \ldots, e_{i-1}$ is in $T$ iff it is in $T'$. Since $T\cup T'$ is connected, the algorithm must have decided to remove $e_i$ from $T$. Hence $e_i$ is in $T'$. Since $T\cup e_i$ has a cycle, pick a cycle of it, which must pass through $e_i$ and hence must contain at least one edge $e_j$ that is not in $T'$. Clearly, $j>i$. Then $T'$ is also minimal for $G-e_j$. On the other hand we may assume by induction on the number of edges in $G$ that the algorithm produces $T'$ when starting with $G-e_j$. That means that at step $i$, removing $e_i$ would cause disconnection. Hence back in the original graph, $T'\cup e_j$ has a cycle that passes through both $e_i$ and $e_j$. Therefore $(T'-e_i)\cup e_j$ is a tree. It has weicght smaller than that of $T'$, contradiction.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .