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: Define Minimum Spanning Tree (MST).
An MST is a subset of edges in a connected, undirected graph that connects all vertices with the minimum possible total edge weight, ensuring no cycles are formed.

Step 2: Analyze Edges and Weights.
The provided edges and their weights are:

- Edge (1, 2): Weight 11

- Edge (3, 6): Weight 14

- Edge (4, 6): Weight 21

- Edge (2, 6): Weight 24

- Edge (1, 4): Weight 31

- Edge (3, 5): Weight 36

To construct an MST, edges are selected in increasing order of weight, provided they do not create a cycle.

Step 3: Final Selection.
The optimal graph will comprise the lowest-weight edges that connect all vertices without forming cycles. This includes edges such as (1, 2), (3, 6), and (4, 6). This selection aligns with option (1).