Question

Suppose a minimum spanning tree is to be generated for a graph whose edge weights are given below. Identify the graph which represents a valid minimum spanning tree?

\[\begin{array}{|c|c|}\hline \text{Edges through Vertex points} & \text{Weight of the corresponding Edge} \\ \hline (1,2) & 11 \\ \hline (3,6) & 14 \\ \hline (4,6) & 21 \\ \hline (2,6) & 24 \\ \hline (1,4) & 31 \\ \hline (3,5) & 36 \\ \hline \end{array}\]
 

Choose the correct answer from the options given below:

• A. 1
• B. 2
• C. 3
• D. 4

Hint:

When finding the minimum spanning tree, always start with the smallest edge weight and continue adding edges without forming cycles.

Answer 1

The Correct Option is A

 

Step 1: Understand the minimum spanning tree. 
A minimum spanning tree (MST) connects all vertices in a graph with the least possible total edge weight, without forming any cycles.

Step 2: Evaluate the given edges and their weights. 
The edges and their corresponding weights are: 

- (1, 2) with weight 11 

- (3, 6) with weight 14 

- (4, 6) with weight 21 

- (2, 6) with weight 24 

- (1, 4) with weight 31 

- (3, 5) with weight 36 

To form a minimum spanning tree, we select the edges with the smallest weights first, ensuring there are no cycles.

Step 3: Conclusion. 
The correct graph will be the one that uses the minimum weight edges, such as (1, 2), (3, 6), and (4, 6), and avoids creating cycles. This corresponds to option (1).