Lecture 1

Minimum Spanning Tree, MST

Low-cost wiring of a network

Graph

Undirected: $V=\{V_1, V_2, ...\}, e\in E:e=\{u,v\}, u,v\in V$

Directed: $E\in V\times V, e\in E, e=(u,v)$

Subgraph: $H=(V_H,E_H),V_H\sube V,E_H\sube E,e_H\in E_H:e_H=\{u,v\},u,v,\in V_H$

Cycle in graph $G$ is a sequence of distinct vertices $V_1,V_2,...,V_k\in V,\{V_i,V_{i+1}\},\{V_k,V_1\}\in E$

Tree: Connected graph without a cycle

Prim’s Algorithm

1. Given $G=(V,E)$, select an arbitrary node and make it the start of $T$
2. For $n-1$ times, add to $T$, the lowest edge from something in $T$ and something not in $T$

Theorem: MST Cut Property

Let $S\subset V(0<|S|<|V|)$, every MST contains the edge $e=\{u,v\},v\in S,u\in V-S$ of minimum weight

Proof: suppose $e\not\in T$, instead $e'\in T$ crosses the cut, then $T$ is not a MST

Note: it is necessary and sufficient

Proof of Prim’s Algorithm

• $n-1$ round and connected → a tree
• Never breaks MST Cut Property

Lecture 2