Minimum spanning tree

Question 1

Why is the spanning tree (V,T) constructed with Kruskal’s

algorithm minimum?

Answer 1

• Consider any edge {i, j} ∈/ T
  –> {i, j} was not added to the graph because it would have
  formed a cycle with the previously added edges
  –> because of the sorting of the edges, all of theses edges are
  shorter (or of the same length)
  → the path optimality conditions are satised for {i, j}
• Because this argument holds for all edges {i, j} ∈/ T, path
  optimality conditions are entirely satised

Question 2

MST (Minumum Spanning Tree) problems are often used in algorithms for other optimization
problems:

Answer 2

• as a relaxation of the TSP
• as a component in Christofides tree heuristic for the TSP
• as a component of a heuristic for the rural postman problem