2
$\begingroup$

Could someone please help me understand lines 5, 6 and 7 in the below proof for Prim's / Kruskal's greedy algorithm of finding minimum spanning tree:

Suppose that either algorithm produces a tree T. Let there exist another spanning tree S with a smaller total weight. Let e be an edge of smallest weight which lies in T but not S.

If we add e to S, we obtain a cycle, from Equivalent Definitions for Tree.

5 - This cycle contains an edge e' which is in S but not T, otherwise T would not be a tree.

6 - So, we replace e' in S with e from T, and obtain a new spanning tree S'.

7 - From the method of construction of T, it follows that the weight of e can not exceed that of e'.

So the total weight of S' does not exceed the total weight of T. Also, S' has one more edge in common with T than S has. We repeat the above procedure, and repeatedly change edges of S for edges of T, and each time the weight of the intermediate graph does not exceed that of T. Thus the weight of T does not exceed that of S, contradicting the definition of S. Hence T must be a minimum spanning tree.

My questions deal with points 5, 6, 7:
5 - If T has e', why is it not a tree?
6- Why does replace e' by e create a new spanning tree and not a new graph?
7- What make sure that w(e) <= w(e')?

Thank you.

2 Answers 2

2

Line $5$: It's a cycle. If all its edges are in $T$, that means $T$ has a cycle, and trees don't have cycles.

Line $6$: A spanning tree is a graph.

Line $7$: Since $e'$ is not in $T$, it was not added because its two vertices were already connected. But if $w(e)\gt w(e')$, then this connection could not have been through $e$, since $e$ wouldn't have been added yet, so the cycle (minus $e'$) would constitute a second connection between the two vertices of $e'$, thus forming a cycle, whereas $T$ is a tree and has no cycles.

  • 0
    @Cody: Unfortunately I don't understand your first question and I don't have an answer to the second one.2012-05-29
1

If T has every e' in the cycle, then in particular is has a cycle. Trees don't have cycles. Thus it wouldn't be a tree.

It is a new graph. The graph happens to be a tree. In fact, because they chose the edge from a cycle, which has the property that every vertex has degree 2, removing 1 edge does not separate any vertex. So it is a spanning tree.

Line 7 alludes the the construction of the trees. You didn't include this here, but in all likelihood it probably has a step like "Of the available edges E, choose e of minimal weight and add it to the tree." It's probably a bit more complicated, but it's something to that effect.

  • 0
    Yes - that's very funny.2012-05-29