Kruskal Mst Fc49Fd

1. **Problem Statement:** Find the minimum cost spanning tree (MST) of the given weighted undirected graph using Kruskal's algorithm and determine the total cost of the MST. 2. **Kruskal's Algorithm Overview:** Kruskal's algorithm finds the MST by sorting all edges in ascending order of weight and adding edges one by one to the MST, avoiding cycles. 3. **List of edges with weights:** - C-B: 12 - B-A: 33 - A-E: 29 - D-E: 14 - C-D: 39 - B-E: 24 - C-A: 20 - D-A: 11 - C-E: 19 - D-B: 32 4. **Sort edges by weight ascending:** $$D-A=11, C-B=12, D-E=14, C-E=19, C-A=20, B-E=24, A-E=29, D-B=32, B-A=33, C-D=39$$ 5. **Select edges for MST:** - Add $D-A=11$ (no cycle) - Add $C-B=12$ (no cycle) - Add $D-E=14$ (no cycle) - Add $C-E=19$ (no cycle) - Add $C-A=20$ (check cycle: vertices C, A, E, D connected, adding $C-A$ connects C and A which are already connected through E and D, so this creates a cycle. Skip.) - Add $B-E=24$ (check cycle: B connected to C, E connected to D and C, adding $B-E$ connects B and E which are already connected through C, so cycle. Skip.) - Add $A-E=29$ (cycle, skip) - Add $D-B=32$ (cycle, skip) - Add $B-A=33$ (cycle, skip) - Add $C-D=39$ (cycle, skip) 6. **Edges in MST:** $$D-A=11, C-B=12, D-E=14, C-E=19$$ 7. **Check if all vertices connected:** Vertices: A, B, C, D, E - $D-A$ connects D and A - $D-E$ connects D and E - $C-E$ connects C and E - $C-B$ connects C and B All vertices connected. 8. **Calculate total cost:** $$11 + 12 + 14 + 19 = 56$$ **Final answer:** The total cost of the minimum spanning tree is $56$.