04 - Costs

Cost Function

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

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

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}$$

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$

Running Time

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