(Latest Revision: Apr 01, 2019) MST Problems First MST Problem:Suppose G=(V,E) is a connected undirected graph whose vertex set V is equal to {1,2,3,4,5,6,7}. Suppose that the edges of G are as follows, sorted by increasing weight. edge {3, 5}, {1, 2}, {3, 7}, {2, 3}, {2,7}, {3,4}, {1,4} {4,5}, {1,6}, {3,6}, {6,7} weight 1, 2, 2, 2, 3, 4, 5, 5, 6, 7, 8 Use Kruskal's algorithm to determine the edges in a min cost spanning tree. In your answer, list the edges in the min cost spanning tree, and their weights, in the order that Kruskal's algorithm would find them.Second MST Problem:Make a drawing of the graph, showing the nodes, edges, and weights. Assuming that node #1 is the start node, list the edges of a min cost spanning tree in the order that they would be found by Prim's algorithm.
(Latest Revision: Apr 01, 2019)
MST Problems
First MST Problem:
Suppose G=(V,E) is a connected undirected graph whose vertex set V is equal to {1,2,3,4,5,6,7}. Suppose that the edges of G are as follows, sorted by increasing weight.
edge {3, 5}, {1, 2}, {3, 7}, {2, 3}, {2,7}, {3,4}, {1,4} {4,5}, {1,6}, {3,6}, {6,7}
weight 1, 2, 2, 2, 3, 4, 5, 5, 6, 7, 8
Use Kruskal's
Second MST Problem:
Make a drawing of the graph, showing the nodes, edges, and weights. Assuming that node #1 is the start node, list the edges of a min cost spanning tree in the order that they would be found by Prim's algorithm.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images
