2
$\begingroup$

a minimum heavyweight spanning tree is a spanning tree in which the heaviest edge is as light as possible. Formally, input : given connected undirected weighted graph, $G$. output : a spanning tree $T$ for $G$ with property that every spanning tree $T'$ for $G$ has some edge $e'$ such that $w(e')\ge w(e)$ for every edge $e$ in $T$.

  1. provide a greedy algorithm to solved the problem.
  2. is every minimum heavyweight spanning tree a minimum spanning tree ?

first thing comes into my mind was using Kruskal's algorithm with $O(|E| \log |V|)$ running time. If I use kruskal's algorithm for 1, the output will guarantee to be a MST, thus 2 will be true? Can someone verify this for me, thanks in advance

$\endgroup$
  • $\begingroup$ Kruskal's (or Prim's) algorithm solves "1" but not "2". $\endgroup$ – Abhishek Bansal Oct 14 '14 at 5:22
  • $\begingroup$ Thinking of a triangle with edges 1,2,2. $\endgroup$ – Bangye Oct 16 '14 at 12:34
  • $\begingroup$ The first is answered here, the second is easily refuted. $\endgroup$ – Raphael Nov 13 '14 at 7:23
0
$\begingroup$

Hints:

  1. Scaling.
  2. Almost every graph would answer this.
$\endgroup$
0
$\begingroup$

1- Kruskal's algorithm can answer the first question (because it's counted as a greedy algorithm ).

2- For the second question i have be thinking like this : let's assume we have graph $G(V,E)$ and let's sort $E$ by Weight in non decreasing order to obtain $E=\{e_{0} ...e_{n}\}$(and we are assuming that the weight values are distinct for simplicity)

Then for us to have a minimum heavyweight spanning tree $T(V,E')$ we must select the the edges in a way that the max edge (edge with maximum weight) in $T$ must be equal to $e_{v-1}$ in the sorted list $E$ which is at index $v-1$ in $E$ thus the edges must look like $E'=\{e_{0}...e_{v-1}\}$

...Now let's assume that we have a minimum spanning tree $T' \neq T$ with lower cost than $T$ then it must have at least one edge $e'_j$ with lower weight than any of $E'$ which makes the sorted list $E'$ not having the lowest $V-1$ weighted edge in $E$ which leads us to constructing a tree $T''$ which don't have any $e′$ such that $w(e′)≥w(e)$ for every edge $e$ in $T$

... Thus $T$ is not a minimum heavyweight spanning tree ... this states that $T = T'$ must behold and every minimum heavyweight spanning tree must be a minimum heavyweight spanning.

NOTE : this is my way of thinking for a solution to the question , it might not be the right answer !

$\endgroup$
  • $\begingroup$ As cautioned by the poster himself/herself, it is indeed false that every minimum heavyweight spanning tree must be a minimum spanning tree. An counterexample is an triangle with weight 1, 2, 2. $\endgroup$ – Apass.Jack Jul 29 '18 at 3:44

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