| Line 23: | Line 23: | ||
A MBST tree is not always a MST. | A MBST tree is not always a MST. | ||
| − | Proof: Suppose we have a spanning tree <math>T</math> which is a MBST of graph \mathbf{G}, 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 \mathbf{G} to form a new graphs \mathbf{G'}. <math>\mathbf{G'} = \mathbf{G} +X</math>. And the possible edges that connect graph \mathbf{G} 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>. S <math>T'</math> is still a spanning tree, and its largest weight remains | + | Proof: Suppose we have a spanning tree <math>T</math> which is a MBST of graph \mathbf{G}, 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 \mathbf{G} to form a new graphs \mathbf{G'}. <math>\mathbf{G'} = \mathbf{G} +X</math>. And the possible edges that connect graph \mathbf{G} 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>. S <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 \mathbf{G'} is not a minimum spanning tree for <math>\mathbf{G'} </math>. End of proof. |
[[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]] | ||
Revision as of 18:44, 20 July 2017
Computer Engineering(CE)
Question 1: Algorithms
August 2013
Solution 1
A MBST tree is not always a MST.
Proof: Suppose we have a spanning tree $ T $ which is a MBST of graph \mathbf{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 \mathbf{G} to form a new graphs \mathbf{G'}. $ \mathbf{G'} = \mathbf{G} +X $. And the possible edges that connect graph \mathbf{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' $. S $ 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 \mathbf{G'} is not a minimum spanning tree for $ \mathbf{G'} $. End of proof.
