Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: Graph Theory / Trees / Minimal Spanning Trees / Kruskal's
algorithm
Posted:
Sep 10, 1999 11:34 AM
|
|
>
> 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
>
The edge set needs to be ordered according to edge weights here, so
if (W(e) is the weight of the edge e, then
W(e_1) <= W(e_2) <= .... <= W(e_{|E(G)|})
> 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
e_1, e_2, ... are the edges of the graph G, indexed as in the beginning
so W(e_1)<= W(e_2)<=...<=W(e_m), where m=|E(G)|.
So for every edge e_i where i< k one of the following holds:
e_i is neither in S nor in T
e_i is in both S and T
e_i is in S but not in T
and e_k is the first edge in the list such that e_k is in T but not in S.
> 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.
So you do not know at this point, what is the index of e,
therefore you do not know how the weights if e and e_k compare. What
you do know, however, is that e is in S but 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.
This is true, since if U would also be a minimal spanning tree,
we would have chosen it instead of S (S was minimal spanning tree
and had as many edges common with T as possible)
>........ 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.
This must be true, since S must have smaller total weight than U,
and the only difference is that e is in S but not in U and
e_k is in U but not in S.
So W(e)<W(e_k), and because of the indexing, smaller weights come earlier
in the list, 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'.
Yes, at the i-th execution of the loop (which was before the k-th,
since i<k, so up till there we only have included edges in T which
are edges in S) we must have rejected e=e_i, since it is not in T.
The only reason we could have done it is that it induced a cycle
with the already existing edges in T. But those edges are also
in S, so e=e_i must induce a cycle in S as well. This gives you
a contradiction with the fact that S is a tree.
This imlies that e_k could not have existed, with other words there is no
edge which is in T but not in S, S=T, the minimal spanning tree
with as many common edges as possible with T is in fact T, so T
itself is a minimal spanning tree.
I hope it helped.
>.....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.
>
|
|
|
|
