Current location - Training Enrollment Network - Mathematics courses - Spanning tree mathematics
Spanning tree mathematics
Using Kruskal algorithm, the problem boils down to finding the minimum spanning tree of undirected weighted graph.

Remove the ring at vertex V3 and arrange the remaining edges in descending order:

V 1V2,V2V6,V2V4,V4V6,V5V6,V 1V4,V3V6,V3V5,V2V3,V4V5,V 1V3 .

Step 1: Add edge V 1V2, including 2 vertices.

Step 2: Add an edge V2V6 with 3 vertices.

Step 3: Add an edge V2V4, which contains 4 vertices.

Step 4: Remove V4V6, otherwise a cycle will be formed. Add V5V6 with 5 vertices.

Step 5: Remove V 1V4, otherwise a cycle will be formed. Add V3V6, including all vertices.

Therefore, the minimum spanning tree includes edges V 1V2, V2V6, V2V4, V5V6 and V3V6.

The final minimum spanning tree is demand, and its cost is 1+2+3+5+7= 18.