Problem 1. MST - Prim's and Kruskal's algorithms
1. Draw minimum spanning tree (MST) in BOLD BLUE using either Kruskal's or Prim's algorithm. Copy that blue edge I draw as many times as needed and twist it as necessary to put on top the edges which should be added to MST (alternatively, you can use WORD features if you know them, to change edge properties in-place).
2. How many edges are in MST? What is the length of MST? (total sum of weights of edges in MST)
3. What are the neighbors in the MST of the node a______and the node f______.
4. What are first six edges that Kruskal's algorithm adds to MST:
5. What are first six edges that Prim’s algorithm adds to MST:
6. By what minimum amount the weight of edge (a,g) should be decreased so that this edge will be added into MST? At least by Out of MST will go the edge:
7. By what minimum amount the weight of edge (a,d) should be increased to push this edge out of MST? At least by_____Inside MST will go the edge:_____