Question

Let G be a connected weighted undirected graph with n nodes and m edges. The weight of edge e is represented as we. We define a minimum-maximum spanning tree to be a spanning tree T that minimizes the quantity

Y = max We eЄT

A minimum-maximum spanning tree has the smallest maximum edge weight of all possible spanning tree.

(a) (3 points) Prove that a minimum spanning tree of graph G is always a minimum- maximum spanning tree for G.

(b) (3 points) Show that a minimum-maximum spanning tree is not necessary a minimum spanning tree by giving a counter-example.

Answer 1

A minimum spanning tree of a graph is always a minimum-maximum spanning tree, but a minimum-maximum spanning tree is not necessarily a minimum spanning tree.

Step-by-step explanation:

Let's prove that a minimum spanning tree of graph G is always a minimum-maximum spanning tree for G:

1. Assume that T is a minimum spanning tree of G.
2. For any spanning tree S of G, the maximum weight of an edge in S is greater than or equal to the maximum weight of an edge in T.
3. This means that T minimizes the quantity Y = max(We), where e belongs to the set of edges in T.

Now, let's show that a minimum-maximum spanning tree is not necessarily a minimum spanning tree:

1. Consider a graph G with n=3 nodes and m=3 edges, where the weights of the edges are 1, 3, and 5.
2. A minimum spanning tree of G would have a weight of 4, obtained by selecting the edges with weights 1 and 3.
3. However, a minimum-maximum spanning tree of G would have a weight of 5, obtained by selecting the edge with weight 5.