Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am having a lot of trouble proving that my idea is actually correct. Can anyone show me a proof sketch or give me some hints as to how to construct the proof? Thanks!
$\begingroup$
$\endgroup$
12
-
2$\begingroup$ Try to construct a counterexample. Not sure that one exists, but for a moment I felt that one does. In any case, this is a good proof strategy. $\endgroup$– Dave ClarkeJun 4, 2012 at 16:39
-
1$\begingroup$ en.wikipedia.org/wiki/… $\endgroup$– Jukka SuomelaJun 4, 2012 at 16:52
-
6$\begingroup$ If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.) $\endgroup$– Tsuyoshi ItoJun 4, 2012 at 17:39
-
2$\begingroup$ @AdenDong if you solved your own question, feel free to self-answer. $\endgroup$– Artem KaznatcheevJun 5, 2012 at 0:47
-
2$\begingroup$ @DaveClarke: "In any case, this is a good proof strategy." -- True. Worked for me. TCS/maths education should focus way more on this back and forth that is inherent to the process. $\endgroup$– RaphaelJun 5, 2012 at 11:15
|
Show 7 more comments
2 Answers
$\begingroup$
$\endgroup$
What follows is taken from Tsuyoshi Ito's comment.
If you know Kruskal’s algorithm for the minimum spanning tree, it is an easy exercise to show that the output of Kruskal’s algorithm is a minimum bottleneck spanning tree. (I think that it is easier than showing that the output of Kruskal’s algorithm is a minimum spanning tree.)
$\begingroup$
$\endgroup$
Given a graph $G(V, A)$, we know that any spanning tree contains an edge in every cutset. Let $S_{min}^{max}$ and $S$ be the minimax weight spanning tree of $G$ and minimum weight spanning tree of $G$ resp. Any edge $e \in S$ is associated with a cutset $C$. Corresponding to cutset $C$,$S_{min}^{max}$ must also contain an edge, say $e'$. Then if $w(e') < w(e)$, we know that replacing $e$ with $e'$ in $S$ will produce a new spanning tree with lower overall weight, thus contradicting our assumption of optimality of $S$. Hence, we can see that the weight of every edge in $S$ is no greater than the weight of a corresponding edge (obtained from the cutset) in $S_{min}^{max}$. Since, we have compared every edge in $S$ but perhaps possibly may not have compared every edge of $S_{min}^{max}$ in the above process for comparison, the max weight edge in $S_{min}^{max}$ has to be atleast as much as much as the max weight in $S$. Hence we can conclude that $S$ itself produces a minimax weight spanning tree.
