4.5. The Minimum Spanning Tree Problem

• A Spanning Tree is a tree that spans all the nodes in a graph
• Given a connected graph G = (V, E) with positive edge weights c_e, a Minimum Spanning Tree is a subset of the edges T ⊆ E such that T is a spanning tree whose sum of edge weights is minimized.

• We need to find the cheapest spanning tree of the graph, which is called the Minimum Spanning Tree as mentioned above

Three simple algorithms that efficiently finds the Minimum Spanning Tree:

• Start with some root node s and greedily grow a tree T from s outward
• At each step, add the cheapest edge e to T that has exactly one endpoint in T
• Similar to Dijkstra’s (but simpler)
• So, in brief:
  • Maintain a set S ⊆ V ,the set on which we have constructed the spanning tree so far
    
  • Initially S = {s}, s the root node
    
  • In each iteration:
    
  • Grow S by one node, adding to S a node v whose cost = min _{e = (u,v):u in S} C_e
    
  • Also add the edge e =(u,v) that satisfies the above formula.

• Start with T = φ,thus T = an empty tree
• Consider edges in ascending order of cost
• Insert edge e in T as long as e doesn't create a cycle when added
• if e creates a cycle, we ignore it and move on to the next node

• Start with T = E, E the set of all the nodes in the graph
• Consider edges in descending order of cost
• Delete edge e from T unless doing so would disconnect T

• The Cut Property :
  • Assume all edge costs are distinct –> The MST is unique
  • Now, let S be any subset of nodes that is neither empty nor equal to V
  • And let edge e = (v,w) be the minimum cost edge with one end in S and the other in V-S
  • Then an spanning tree contains the edge e
  • This straight-out-of-the-book statement is the cut property of the Minimum Spanning Tree.Proof:See book
  • So, we can insert nodes in the MST as long as we don't create cycle when doing so.
• Prim's and Kruskal's algorithms produce a Minimum spanning tree of the graph G
  
• The Cycle property:
  • Let C be any cycle, and let f be the maximum cost edge belonging to C
  • Then MST does not contain f.
  • So, we can delete a node from the MST as long as we don't disconnect our MST
• The Reverse-Delete Algorithm produces a Minimum Spanning Tree of the graph G