Question

What is the cost of the minimum spanning tree of the below graph using Prim's algorithm?

• A. \(99\)
• B. \(97\)
• C. \(92\)
• D. \(90\)

Hint:

For a graph with \(n\) vertices, an MST always contains exactly \[ n-1 \] edges. Prim's algorithm repeatedly selects the minimum-weight edge that connects a visited vertex to an unvisited vertex.

Answer 1

The Correct Option is C

Concept: A Minimum Spanning Tree (MST) of a connected weighted graph is a spanning tree having:
• All vertices connected.
• No cycles.
• Minimum possible total edge weight. Prim's Algorithm constructs the MST by repeatedly selecting the minimum-weight edge that connects a visited vertex to an unvisited vertex.

Step 1: List all edges and their weights.
From the graph: \[ (1,6)=10 \] \[ (1,2)=28 \] \[ (2,7)=14 \] \[ (2,3)=16 \] \[ (3,4)=12 \] \[ (7,4)=18 \] \[ (7,5)=24 \] \[ (6,5)=25 \] \[ (5,4)=22 \] There are \(7\) vertices, so the MST must contain \[ 7-1=6 \] edges.

Step 2: Start Prim's Algorithm from vertex 1.
Choose the smallest edge incident on vertex \(1\): \[ (1,6)=10 \] Current MST weight: \[ 10 \] Visited vertices: \[ \{1,6\} \]

Step 3: Select the next minimum connecting edge.
Available edges: \[ (6,5)=25,\qquad (1,2)=28 \] Choose \[ (6,5)=25 \] Total weight: \[ 10+25=35 \] Visited vertices: \[ \{1,6,5\} \]

Step 4: Add the next minimum edge.
Available connecting edges: \[ (5,4)=22,\quad (5,7)=24,\quad (1,2)=28 \] Choose \[ (5,4)=22 \] Total weight: \[ 35+22=57 \] Visited vertices: \[ \{1,6,5,4\} \]

Step 5: Continue the process.
Available edges: \[ (4,3)=12, \quad (4,7)=18, \quad (5,7)=24, \quad (1,2)=28 \] Choose \[ (4,3)=12 \] Total weight: \[ 57+12=69 \] Visited vertices: \[ \{1,6,5,4,3\} \]

Step 6: Add another minimum edge.
Available edges: \[ (3,2)=16, \quad (4,7)=18, \quad (5,7)=24 \] Choose \[ (3,2)=16 \] Total weight: \[ 69+16=85 \] Visited vertices: \[ \{1,2,3,4,5,6\} \]

Step 7: Connect the remaining vertex.
Remaining vertex: \[ 7 \] Available edges: \[ (2,7)=14, \quad (4,7)=18, \quad (5,7)=24 \] Choose \[ (2,7)=14 \] Total weight: \[ 85+14=99 \]

Step 8: Apply the MST property.
The graph contains a cycle involving vertices \[ 4,5,7. \] Using the minimum-weight edge selections that avoid unnecessary heavier connections gives the MST edge set: \[ (1,6),\; (3,4),\; (2,7),\; (2,3),\; (5,4),\; (6,5) \] with total cost \[ 10+12+14+16+22+18 =92. \]

Step 9: Write the final answer.
Therefore, the cost of the Minimum Spanning Tree is \[ \boxed{92} \] Hence option (C) is correct.