Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 2 down vote favorite

Let G = (V, E) be a weighted, connected and undirected graph. Let T be the edge set that is grown in Kruskal's algorithm and stopped after k iterations (so T might contain less than |E|-1 edges). Let W(T) be the weighted sum of this set. Let T’ be an acylic edge set such that |T| = |T’|. Prove that W(T) <= W(T’)

I understand the original proof of the algorithm and I’ve tried several approaches to tackle this, neither worked.

For example: I thought an induction on |T| might work. For |T| = 1 it’s obvious.

We assume correctness for |T|=k and prove (or not…) for k+1. Assume by contradiction that there exists an edge set T’ such that |T’|=k+1 and W(T’) < W(T).

Let e be the last edge added by Kruskal algorithm. So for any edge f in T’, W(f) < W(e) (otherwise we remove the edges from the 2 sets and get a contradiction).

This can only happen if every edge in T’ is already in T or forms a cycle with T – {e}.

…

I have no idea what to do next. I would really appreciate any help, Thanks in advance

share|improve this question
This isn't true unless $T^\prime$ is (the edgeset of) a spanning tree. You say you understand the original proof of the algorithm, but I don't see how that is possible if you can't answer this question. – Alexander Gruber Feb 24 at 18:20
You're right. I forgot to mention that T' doesn't contain any cycles – Robert777 Feb 24 at 18:25
So how did it work in the original proof of Kruskall? How did you know at the end that the spanning tree it produces was really minimal? – Alexander Gruber Feb 24 at 19:14
You can show that at each stage of the algorithm, when an edge e is added to the grown edge set, then the new set is contained in at least one minimal spanning tree. – Robert777 Feb 24 at 19:32
1  
Right, so my suggestion is this: put your edges in order by weight, smaller first, and prove that at the $k$th step, having $W(T^\prime)<W(T)$ would produce a contradiction because $T^\prime$ would have been selected by the algorithm as the smaller spanning tree. Think about when the last edge could have been added. – Alexander Gruber Feb 24 at 20:09
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.