There are two graphs in the question. Solve for Minimum spanning trees using both Kruskal's algorithm and Prim's algorithm.
For two graphs, your homework script will have four solutions (2 solutions per graph).
note: click on the picture so that you can see the full picture
Answers
Answer:
Explanation:
What is a Spanning Tree?
Given an undirected and connected graph , a spanning tree of the graph is a tree that spans (that is, it includes every vertex of ) and is a subgraph of (every edge in the tree belongs to )
What is a Minimum Spanning Tree?
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.
Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching. Other practical applications are:
Cluster Analysis
Handwriting recognition
Image segmentation