Minimum Spanning Trees

Preview

1. What is the minimum spanning tree of a graph?
2. How can Prim’s algorithm be used to find the minimum spanning tree of a graph?
3. Can Kruskal’s algorithm be used to find the minimum spanning tree of a weighted directed graph?
4. What is the relationship between the minimum spanning tree and the shortest path tree in a graph?
5. How can we prove that the minimum spanning tree of a weighted undirected graph is unique?

Explain

Minimum Spanning Tree (MST) is a subset of edges in a weighted undirected graph that connects all the vertices (nodes) together without any loops and with the minimum possible total edge weight.

Consider the following graph:

         2
   (1)--------(2)
   / \        / \
3/    4\   6/    \5
 /       \ /       \
(4)------(3)--------(5)
         7          8

To find the MST of this graph, we can use the Kruskal’s algorithm, which follows the following steps:

1. Sort all the edges in ascending order of their weights.
2. Pick the smallest edge and check if it forms a cycle with the MST formed so far. If not, add the edge to the MST.
3. Repeat step 2 until all the vertices are included in the MST.

Using Kruskal’s algorithm, we can find the MST of the above graph as:

   (1)--------(2)
             /   
          6/    
           /      
        (3)        
         | \      
         |5  \8            
         |   \     
        (5)---(4)         

Here, the MST has four edges with a total weight of 2+6+5+8=21. This is the minimum possible weight for a spanning tree of this graph.

Keypoint

1. A minimum spanning tree is a tree that spans all the nodes of a weighted graph, with the minimum possible total edge weight.
2. There are various algorithms to find the minimum spanning tree, including Prim’s algorithm, Kruskal’s algorithm, and Boruvka’s algorithm.
3. The minimum spanning tree has applications in various fields such as network design, transportation planning, and clustering problems.
4. In a minimum spanning tree, there is only one unique path between any two nodes.
5. The minimum spanning tree is a subgraph of the original graph, where the number of edges is one less than the number of nodes.
6. The minimum spanning tree is a connected graph, where all nodes are reachable from any other node of the tree.
7. The cost of minimum spanning tree is the sum of the weights of all edges in the tree.
8. If the graph is not connected, it is impossible to create a minimum spanning tree.
9. In a weighted graph with negative edge weights, the minimum spanning tree may not be unique.
10. The minimum spanning tree is a special case of a minimum spanning forest, where multiple trees can be created to span all nodes of the graph.

Review

1. What is a Minimum Spanning Tree (MST)?
   Answer: A Minimum Spanning Tree is a tree that connects all the vertices of a graph with the minimum total weight of edges.

2. How can you find a Minimum Spanning Tree of a graph?
   Answer: One way to find a Minimum Spanning Tree is by using Kruskal’s algorithm or Prim’s algorithm.

3. If two edges have the same weight in a graph, which one should be chosen in the Minimum Spanning Tree?
   Answer: Either one of the two edges can be chosen in the Minimum Spanning Tree, as long as the total weight of the tree is minimized.

4. Can a graph have multiple Minimum Spanning Trees?
   Answer: Yes, if there are multiple edges with the same minimum weight, then there can be multiple Minimum Spanning Trees.

5. What is the time complexity of finding a Minimum Spanning Tree using Prim’s algorithm?
   Answer: The time complexity of Prim’s algorithm is O(E log V), where E is the number of edges and V is the number of vertices in the graph.