To solve the problem of finding the minimum spanning tree (MST) of the given weighted graph, we will use Kruskal’s algorithm or Prim’s algorithm. Here is how the solution proceeds:

Kruskal’s Algorithm (Outline):

1. List all edges with their weights in ascending order.
2. Start adding edges to the tree, ensuring no cycles are formed.
3. Stop when all vertices are connected.

Step-by-Step Solution:

1. Edges in ascending order:

   • $v_3 \to v_4: 2$
   • $v_4 \to v_1: 7$
   • $v_5 \to v_1: 4$
   • $v_6 \to v_5: 8$
   • $v_3 \to v_2: 5$
   • $v_7 \to v_6: 13$
   • $v_7 \to v_4: 15$
   • $v_4 \to v_2: 10$
   • $v_2 \to v_7: 18$
   • $v_2 \to v_1: 20$
   • $v_6 \to v_7: 19$

2. Select edges to form the MST (start with the smallest weights):

   • Include $v_3 \to v_4$ ($2$): Forms $\{v_3, v_4\}$.
   • Include $v_4 \to v_1$ ($7$): Forms $\{v_1, v_3, v_4\}$.
   • Include $v_5 \to v_1$ ($4$): Forms $\{v_1, v_3, v_4, v_5\}$.
   • Include $v_6 \to v_5$ ($8$): Forms $\{v_1, v_3, v_4, v_5, v_6\}$.
   • Include $v_3 \to v_2$ ($5$): Forms $\{v_1, v_2, v_3, v_4, v_5, v_6\}$.
   • Include $v_7 \to v_6$ ($13$): Forms $\{v_1, v_2, v_3, v_4, v_5, v_6, v_7\}$.

3. MST Edges:

   • $v_3 \to v_4 (2)$,
   • $v_4 \to v_1 (7)$,
   • $v_5 \to v_1 (4)$,
   • $v_6 \to v_5 (8)$,
   • $v_3 \to v_2 (5)$,
   • $v_7 \to v_6 (13)$.

4. Total Weight:

   • $2 + 7 + 4 + 8 + 5 + 13 = 39$.

Why It’s Minimum?

The MST is formed using Kruskal’s or Prim’s algorithm, which ensures:

1. No cycles are formed.
2. All vertices are connected.
3. The total weight of the selected edges is minimized.

Would you like a graphical illustration or further clarifications?

Related Questions:

1. How does Prim’s algorithm differ from Kruskal’s in solving this graph?
2. What are the applications of minimum spanning trees in real life?
3. How can cycle formation be avoided in Kruskal’s algorithm?
4. What is the time complexity of Kruskal’s algorithm?
5. Can the MST change if the weights of certain edges increase slightly?

Tip:

Always verify your MST using both Kruskal's and Prim's algorithms to cross-check the total weight and edges.