| (5 intermediate revisions by the same user not shown) | |||
| Line 19: | Line 19: | ||
August 2013 | August 2013 | ||
</center> | </center> | ||
| + | ---- | ||
| + | [[ECE-QE_CE1-2013|Back to QE CE question 1, August 2013]] | ||
| + | ---- | ||
| + | |||
| + | '''Problem 3.''' | ||
| + | The minimum bottle neck spanning tree (MBST) is a spanning tree that seeks to minimize the use of most expensive (the largest weight) edge in the tree. More specifically, for a tree <math>T</math> over a graph G, we define <math>e</math> to be a bottleneck edge of <math>T</math> if it's an edge with the largest weight. Note, multiple edges may have the same weight. The tree <math>T</math> is an MBST if it is a spanning tree and there is no other spanning tree of G with a cheaper bottleneck edge. Prove or disprove that an MBST for a graph G is always a minimum spanning tree for G. | ||
| + | |||
| + | ---- | ||
| + | ===Share your solutions below.=== | ||
---- | ---- | ||
===Solution 1=== | ===Solution 1=== | ||
| − | A | + | A minimum bottle neck spanning tree (MBST) is not always a minimum spanning tree MST. |
Proof: Suppose we have a spanning tree <math>T</math> which is a MBST of <math>G</math> , and <math>T</math> is also a MST. The bottle neck is edge <math>e</math> with weight <math>w</math>. Then I have another vertex <math>X</math> that will be connected to the graph <math>G</math> to form a new graphs <math>G'</math>. <math>G' = G + X</math>. And the possible edges that connect graph <math>G'</math> and new vertex <math>X</math> has weights <math>w_1, w_2, ... W_x</math>, and each is no greater than the bottle neck weight <math>w</math>. Using any of the edges from <math>w_1, w_2, ... W_x</math>, I get a new tree <math>T'</math>. So <math>T'</math> is still a spanning tree, and its largest weight remains <math>w</math>, so <math>T'</math> is also an MBST. However, among these edges that I can choose to span the tree, only the one that has the smallest weight will be a MST, by definition. So an MBST for a graph <math>G'</math> is not a minimum spanning tree for <math>G'</math>. End of proof. | Proof: Suppose we have a spanning tree <math>T</math> which is a MBST of <math>G</math> , and <math>T</math> is also a MST. The bottle neck is edge <math>e</math> with weight <math>w</math>. Then I have another vertex <math>X</math> that will be connected to the graph <math>G</math> to form a new graphs <math>G'</math>. <math>G' = G + X</math>. And the possible edges that connect graph <math>G'</math> and new vertex <math>X</math> has weights <math>w_1, w_2, ... W_x</math>, and each is no greater than the bottle neck weight <math>w</math>. Using any of the edges from <math>w_1, w_2, ... W_x</math>, I get a new tree <math>T'</math>. So <math>T'</math> is still a spanning tree, and its largest weight remains <math>w</math>, so <math>T'</math> is also an MBST. However, among these edges that I can choose to span the tree, only the one that has the smallest weight will be a MST, by definition. So an MBST for a graph <math>G'</math> is not a minimum spanning tree for <math>G'</math>. End of proof. | ||
| Line 29: | Line 38: | ||
A MBST tree is not a minimum spanning tree for <math>G</math>, ABST may not contain the lightest edge. A counter example is showing in figure below: <br> | A MBST tree is not a minimum spanning tree for <math>G</math>, ABST may not contain the lightest edge. A counter example is showing in figure below: <br> | ||
[[File:Q3-MBST-example.png|600px]] | [[File:Q3-MBST-example.png|600px]] | ||
| + | |||
| + | |||
| + | <br> | ||
| + | |||
| + | <font color="red"><u>'''Comments on Solution 2:'''</u> | ||
| + | |||
| + | This is a good counter example that showing MBST is not a MST. | ||
| + | |||
| + | <br> | ||
| + | ---- | ||
[[ECE-QE_CE1-2013|Back to QE CE question 1, August 2013]] | [[ECE-QE_CE1-2013|Back to QE CE question 1, August 2013]] | ||
[[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]] | [[ECE_PhD_Qualifying_Exams|Back to ECE Qualifying Exams (QE) page]] | ||
Latest revision as of 16:07, 23 August 2017
Computer Engineering(CE)
Question 1: Algorithms
August 2013
Back to QE CE question 1, August 2013
Problem 3. The minimum bottle neck spanning tree (MBST) is a spanning tree that seeks to minimize the use of most expensive (the largest weight) edge in the tree. More specifically, for a tree $ T $ over a graph G, we define $ e $ to be a bottleneck edge of $ T $ if it's an edge with the largest weight. Note, multiple edges may have the same weight. The tree $ T $ is an MBST if it is a spanning tree and there is no other spanning tree of G with a cheaper bottleneck edge. Prove or disprove that an MBST for a graph G is always a minimum spanning tree for G.
Solution 1
A minimum bottle neck spanning tree (MBST) is not always a minimum spanning tree MST.
Proof: Suppose we have a spanning tree $ T $ which is a MBST of $ G $ , and $ T $ is also a MST. The bottle neck is edge $ e $ with weight $ w $. Then I have another vertex $ X $ that will be connected to the graph $ G $ to form a new graphs $ G' $. $ G' = G + X $. And the possible edges that connect graph $ G' $ and new vertex $ X $ has weights $ w_1, w_2, ... W_x $, and each is no greater than the bottle neck weight $ w $. Using any of the edges from $ w_1, w_2, ... W_x $, I get a new tree $ T' $. So $ T' $ is still a spanning tree, and its largest weight remains $ w $, so $ T' $ is also an MBST. However, among these edges that I can choose to span the tree, only the one that has the smallest weight will be a MST, by definition. So an MBST for a graph $ G' $ is not a minimum spanning tree for $ G' $. End of proof.
Solution 2
A MBST tree is not a minimum spanning tree for $ G $, ABST may not contain the lightest edge. A counter example is showing in figure below:
Comments on Solution 2:
This is a good counter example that showing MBST is not a MST.
