Math Forum Discussions

Ms. Confusing

Posts: 2
Registered: 12/6/04

Graph Theory / Trees / Minimal Spanning Trees / Kruskal's algorithm
Posted: Sep 9, 1999 1:35 PM

Plain Text

Hi!
Could you take a look at this ... can you find this book? Is there a
mistake or am I just too confused ... this is not supposed to be so
hard. I have seen some different proofs of this algorithms.

Lately I saw it in the book called "Discrete Mathematics" by Kenneth
A. Ross and Charles R.B.Wright (paper back version, page 412-413).

Kruskal's algorithm in this book is like this:
Set E to empty set
For j=1 to |E(G)|
If E union {e_j} is acyclic replace E by E union {e_j}
End for
End

Graph is G, T is minimal spanning tree whose edge set is E.

I understand the first part of the proof that T is spanning tree, but
when one must show that T is minimal ... I get into trouble ... I even
started to think there is mistake in my book ... last paragraph of the
proof ... should I change S and T around ...

Here is the version of the book (and questions) ...
To show that T is actually minimal spanning tree, consider a minimal
spanning tree S of G that has as many edges as possible in common with
T. We will show that S=T. Suppose not, and let e_k be the first edge
on the list e_1,...,e_m (are these the edges of T?) that is in T but
not in S.Let S*=S union e_k. In view of Theorem 2(d), S* contains a
cycle, say C, which must contain e_k because S itself is acyclic.
Since T is also acyclic, there must be some other edge e in C that is
not in T. Note that e is an edge of S. Now delete e from S* to get
U=S*\e=(S union e_)\e. By Theorem 1, U is connected, and since it has
the same number of edges as S, U is spanning tree by Theorem 3.
Moreover, U has one more edge, namely e_k, in common with T than S
has. Because of the choice of S, U is not minimal spanning tree. By
comparing the weights of S and U we conclude that W(e)<W(e_k), and so
e=e_i for some i<k.
(That part is OK, but at the very end ... e=e_i ... and e<k ... and e
is not in T ... a little bit of confusing, I suppose that at the very
start the edge list consists of edges in T, and in S there are other
edges as well, and then those edges of T that are in T before edge
e_k)
(Now comes the problem)
Now e is not in T, so it must have been rejected at the j=i stage for
the reason that at that time E union e contained a cycle, say C'. All
edges in E at that stage were in S, by our choice of e_k as the first
edge in S (should it be T??) but not in T (should it be S??). Since e
is also in S, C' is a cycle in S, which is a contradiction. Thus S=T,
as we wanted to show.

Thanks.