03. Minimum Cost Spanning Trees

Cost Function

Let $G$ be a graph with cost function $c$ on edges so

$$c(e)>0\text{ for all }e\in E(G)$$

Link to original

Minimum Cost Spanning Tree

Let $G=(V,E)$ be a connected graph
Let $c:E\to (0,\infty )$ be a cost function

Let $T$ be a Spanning Tree of $G$ then

$T$ is a Minimum Cost Spanning Tree (MCST) if

$$c(T)=\sum _{e\in E(T)}c(e)\text{ is minimum}$$

Link to original

Kruskal's Algorithm

Let $G=(V,E)$
Let $c:E\to (0,\infty )$ be a cost function

Start with

$$H_0=(V,\varnothing )$$

For $H_i$ then
If there exists edge $e$ of $G$ where $e\notin H_i$ such that

$$H_i+e\text{ is acyclic}$$

then
Let $e$ be cheapest such edge then set

$$H_{i+1}=H_i+e$$

and continue

Then denote $H_t$ for the final graph $H$

Link to original

Kruskal's Algorithm and MCST

Let $G$ be a connected graph
Let $c(e)$ be positive for each edge then

Kruskal’s Algorithm ends with MCST for $G$

Proof

As $V(H_t)=V(H_0)=V$ then $H_t$ then $H_t$ is spanning
Hence acyclic by construction

Suppose $H_t$ is not connected then
Let $C$ be a component of $H_t$

As $C$ does not contain all vertices then
Let $v$ be inside $C$ and $w$ be outside $C$
So $G$ contains a $v$-$w$ path which must leave $C$

Hence there exists edge $e=xy$ of $G$ with $x$ inside $C$ and $y$ outside
Hence $x$ and $y$ are not connected in $H_t$ hence $H_t+e$ is acyclic

This contradicts stopping rule in algorithm
Hence $H_t$ is a spanning tree

Thus $t=n-1$ where $n=|G|$

Let ${\mathcal{P}}_i$ be proposition such that exists MCST $T$ of $G$ with $H_i\subseteq T$ for $0\le i\le n-1$
So ${\mathcal{P}}_0$ holds as $H_0$ has no edges

If ${\mathcal{P}}_{n-1}$ holds then $H_{n-1}\subseteq T$ then
Both $H_{n-1}$ and $T$ have $n-1$ edges so

$$H_{n-1}=T$$

Thus $H_{n-1}$ is a MCST

Suppose $i<n-1$ and $P_i$ holds so

$$H_i\subseteq T$$

for some MCST $T$ of $G$

Let $e$ be the next edge added by algorithm so

$$H_{i+1}=H_i+e$$

If $e$ is an edge of $T$ then

$$H_{i+1}\subseteq T$$

Let $e=xy$ then $T$ contains $x$-$y$ path
Hence $T+e$ contains cycle $C$

As $H_{i+1}$ is acyclic then exists edge $f$ of $H$ not in $H_{i+1}$
Let $T^{\prime }=T+e-f$

As $H_{i+1}\subseteq T^{\prime }$ by construction then

$$H_{i+1}=H_i+e\subset T+e$$

where $f$ is not in $H_{i+1}$

As $T+e$ has $n-1$ edges then by Relation of connectivity and edges to a tree it is a tree
Hence $T+e$ is acyclic

Thus $f$ was a possible edge to add at step $i$ and by definition then

$$c(e)\le c(f)$$

Hence

$$c(T^{\prime })\le c(T)$$

and as $T$ has minimum cost then so does $T^{\prime }$

Link to original

Cyclic Property of Adding Edge to Graph

Let $G$ be a graph

Adding edge $e=xy$ to graph $G$ creates cycle $⟺$ $H$ contains $x$-$y$ path

Link to original

Running Time

For Kruskal’s Algorithm then if $G$ has $n$ vertices and $m$ edges then there are $nm$ steps

Link to original