Minimum Spanning Tree (MST)

Go to previous page

Given connected graph G, weight function $w: E(G) \rightarrow \mathbb(R)$

Goal: find a spanning tree whose total edge weight minimized.

Notation: $w(e)$ is the weight of $e$. If $H$ is a subgraph of $G$, $$w(H) = \sum_{e\in E(G)} w(e)$$

Prim's Algorithm

  1. Let $v$ be any vertex. Let $T$ be the tree with just $v$.
  2. While $T$ is not a spanning tree.
    1. look at all the edges in the cut induced by $V(T)$
    2. Pick $e=uv$ to be an edge of smallest weight in the cut (say $u\in V(T), v \not \in V(T)$)
    3. Add $v$ to $V(T)$, add $e$ to $E(T)$

Theorem: Prim's algorithm produces a MST.

Proof:

Let $T_1, T_2, T_3, \cdots, T_n$ be the trees produced by the algorithm at each step, where the order of the edges added is $e_1, e_2, \cdots, e_{n-1}$, i.e. $T_{k+1} = T_k + e_k$

Prove by induction on k that each $T_k$ is a subgraph of a MST. If so, then $T_n$ is a spinning tree contained in a MST, so $T_n$ is a MST


Base case: For $k=1$, $T_1$ is just one vertex, which is any MST

Induction Hypotheses: Assume $T_k$ is a subgraph of a MST, $T_k$ for some k

Induction Step: Show $T_{k+1}$ is a subgraph of some MST.

If $e_k \in E(T^{*})$, then $T_{k+1}$ is a subgraph of $T^{k}$ and we are done!

Assume $e_k \not \in E(T^{*}$), then $T^{*} + e_k - e'$ is also a spanning tree.

The algorithm chose $e_k$ when looking at the cut induced by $V(T_k)$, so $w(e_k) \le w(e').$

If $w(e_k) < w(e')$, then $w(T') = w(T^{*}) + w(e_k) - w(e') < w(T^*)$ which is impossible, since $w(T') is smaller than the weight of a MST.

If $w(e_k) = w(e')$, then $w(T) = w(T^*)$, so $T'$ is a MST. And $T'$ contains $T_{k+1}$ as a subgraph (since it contains $e_k$)

This completes the induction.


Travelling Salesman Problem (TSP)

Goal: Find a Hamilton cycle (cycle that uses all vertices) of minimum weight.

No polynomial time algorithm is known so far. Restrict weights to Euclidean distance.

Approximate Algorithm:
  1. find the minimum spanning tree T
  2. double all edges
  3. find an Eulidean circuit
  4. find a hamilton cycle by skipping repeated vertices (take the short cut)

Theorem: The approx. algorithm produces a cycle whose weigth is at most twice the best possible Hamilton cycle.

Proof: Let $C^*$ be a min. weigth Hamilton cycle, $C^* -e$ is a spanning tree. so $w(c^*) \ge w(T)$

If C is the cycle from the approximate algorithm, then the $w(c) \le 2w(T)$ since we are taking short cut using triangle-inequality. so $w(c) \le 2w(c^*)$

Back To Top