6
$\begingroup$

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!

$\endgroup$
  • 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 Clarke Jun 4 '12 at 16:39
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – Jukka Suomela Jun 4 '12 at 16:52
  • 5
    $\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 Ito Jun 4 '12 at 17:39
  • 2
    $\begingroup$ @AdenDong if you solved your own question, feel free to self-answer. $\endgroup$ – Artem Kaznatcheev Jun 5 '12 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$ – Raphael Jun 5 '12 at 11:15
5
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

By finding a median edge of a graph - it can be done in linear time.

I think this answer from stackoverflow can be helpful.

$\endgroup$
  • 1
    $\begingroup$ Could you give more details? You seem to be saying that medians (in this sense?), component identification and this question are all related to each other, but I can't even see the connection between any pair of those concepts. $\endgroup$ – David Richerby Nov 22 '17 at 12:42
  • $\begingroup$ @DavidRicherby I edited my answer: 1. the answer link was wrong one, corrected - sorry! 2. median = a median edge of a graph (an edge that half of the edges are lighter and half are heavier than it). $\endgroup$ – sosolo Nov 24 '17 at 10:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.