Minimum Spanning Tree Problem 4. [4 points] Minimum Spanning Tree Problem One of
ID: 664273 • Letter: M
Question
Minimum Spanning Tree Problem
4. [4 points] Minimum Spanning Tree Problem One of the basic motivations behind the Minimum Spanning Tree Problem is the goal of designing a spanning network for a set of nodes with minimum total weight. Here we explore another type of objective: designing a spanning network for which the edge with the highest weight is as small as possible. Specifically. let (7 = (V E) be a connected graph with n vertices, in edges, and positive edge costs that you may assume are all distinct. Let (V. T) be a spanning tree of G where T E. We define the bottleneck edge of T to be the edge of T with the greatest weight. A spanning tree T of G is a minimum-bottleneck spanning tree if there is no spanning tree T? of G with a smaller bottleneck edge. Are the following statements true or false? If it is true, give a short explanation (in no more than five sentences please) If it is false, give a counterexample (a) [2 points] Is every minimum-bottleneck tree of G a minimum spanning tree of G? (b) [2 points] Is every minimum spanning tree of G a minimum-bottleneck tree of G?Explanation / Answer
a) The anser is false.
Explanation with 3 to 4 sentences:
Every MST (Minimum Spanning Tree) must be a MBST (Minimum Bottlenext Spanning Tree) but NOT VICE VERSA. Hence every MBST is NOT a MST. An example graph with
The edges and their weights are listed as follows:
ab = 10, bc = 20, af = 5, cf = 90, df = 75 and ed = 11
*********************************************************************************************
b) True.
Explanation with 3 to 4 sentences:
Every MST (Minimum Spanning Tree) must be a MBST (Minimum Bottleneck Spanning Tree).
After redisgning the same example got a new spanning network as follows:
af = 5, ab = 10, bc = 20, cd=30, ed = 11
Here we are going to acheive a heighest weight of cd = 30 instead of
90 - a huge savings on the weight cost.