Exercise 4 DESIGN AND ANALYSIS ALGORETHEM COURES Question

  Exercise 4 :    (DESIGN AND ANALYSIS ALGORETHEM COURES )  

• Question 2: Given a graph G(V, E) with positive and pairwise different weights on the edges. Show that the minimum spanning tree is unique.

Remarks: All the graphs here are without self loops and parallel edges, and anti-parallel edges. In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit.

Solution

Suppose T1 and T2 are distinct minimum spanning trees, then consider the edge of minimum weight that is contained in only one of T1 or T2. Without loss of generality, this edge appears only in T1, and we can call it e1.

Then T2 {e1} contains a cycle, and so one of the edges of this cycle, call it e2, is not in T1.

Note that w(e1) < w(e2) and T=T2 {e1}{e2} is a spanning tree. The total weight of T is smaller than the total weight of T2, but this is a contradiction, since we have supposed that T2 is a minimum spanning tree.

Hence it is proved that a graph with positive and pairwise different weights on the edges can have a single minimum spanning tree.