A spanning tree t of g is a minimum-bottleneck spanning


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 cost. Here we explore another type of objective: designing a spanning network for which the most expensive edge is as cheap as possible.

Specifically, let = (E) be a connected graph with vertices, edges, and positive edge costs that you may assume are all distinct. Let = (E′) be a spanning tree of G; we define the bottleneck edge of to be the edge of with the greatest cost.

A spanning tree of is a minimum-bottleneck spanning tree if there is no spanning tree T′ of with a cheaper bottleneck edge.

(a) Is every minimum-bottleneck tree of a minimum spanning tree of G? Prove or give a counterexample.

(b) Is every minimum spanning tree of a minimum-bottleneck tree of G? Prove or give a counterexample.

Solution Preview :

Prepared by a verified Expert
Business Management: A spanning tree t of g is a minimum-bottleneck spanning
Reference No:- TGS02928993

Now Priced at $10 (50% Discount)

Recommended (91%)

Rated (4.3/5)