Mst Kruskal Prim 63C283

1. **Problem 1: Minimum Spanning Tree (MST) using Kruskal's Algorithm for Graph 1** Given edges and weights, find MST by sorting edges ascending by weight and adding edges without forming cycles. Edges sorted by weight: (B-C:1), (A-D:2), (C-F:3), (E-F:1), (H-I:2), (D-E:7), (B-E:5), (A-B:5), (E-H:3), (F-I:4), (G-H:8), (D-G:6), (B-F:8), (C-D:2), (A-C:4) Step 1: Add (B-C) weight 1 Step 2: Add (E-F) weight 1 Step 3: Add (A-D) weight 2 Step 4: Add (H-I) weight 2 Step 5: Add (C-D) weight 2 Step 6: Add (E-H) weight 3 Step 7: Add (C-F) weight 3 Step 8: Add (F-I) weight 4 Step 9: Add (A-B) weight 5 Stop adding edges when all vertices connected. Total MST weight = $1+1+2+2+2+3+3+4+5=23$ 2. **Problem 2: MST using Kruskal's Algorithm for Graph 2** Edges sorted ascending: (F-G:5), (G-D:6), (A-B:6), (D-E:6), (A-G:7), (C-D:7), (B-C:8), (E-F:8), (B-F:8), (B-D:9), (F-D:9) Step 1: Add (F-G) weight 5 Step 2: Add (G-D) weight 6 Step 3: Add (A-B) weight 6 Step 4: Add (D-E) weight 6 Step 5: Add (A-G) weight 7 Step 6: Add (C-D) weight 7 Adding any other edge forms cycle. Total MST weight = $5+6+6+6+7+7=37$ 3. **Problem 3: MST for Graph 3** Edges sorted ascending: (E-F:1), (B-C:4), (H-I:2), (A-D:2), (C-F:3), (E-H:3), (F-I:4), (A-B:5), (B-E:5), (D-G:6), (D-E:7), (G-H:8) Step 1: Add (E-F) weight 1 Step 2: Add (H-I) weight 2 Step 3: Add (A-D) weight 2 Step 4: Add (C-F) weight 3 Step 5: Add (E-H) weight 3 Step 6: Add (F-I) weight 4 Step 7: Add (B-C) weight 4 Step 8: Add (A-B) weight 5 Step 9: Add (B-E) weight 5 Stop when all vertices connected. Total MST weight = $1+2+2+3+3+4+4+5+5=29$ 4. **Problem 4: MST using Prim's Algorithm for Graph 4** Start from vertex 1. Step 1: Choose edge (1-6) weight 20 (minimum adjacent to 1) Step 2: Choose edge (6-2) weight 25 (minimum adjacent to 1 or 6) Step 3: Choose edge (2-5) weight 15 (minimum adjacent to 1,6,2) Step 4: Choose edge (5-4) weight 30 (minimum adjacent to 1,6,2,5) Step 5: Choose edge (4-3) weight 10 (minimum adjacent to 1,6,2,5,4) Total MST weight = $20+25+15+30+10=100$ **Summary:** - Problem 1 MST weight: 23 - Problem 2 MST weight: 37 - Problem 3 MST weight: 29 - Problem 4 MST weight: 100 Each MST constructed step-by-step as above.