Minimum Spanning Tree

Problem

Given an undirected graph $G = (V, E)$, each edge $e \in E$ has an edge cost $W_e$. We want a tree that spans all $n$ vertices (has $n-1$ edges) with the minimum total cost.

Insert picture examples here

Preliminaries

Simple Cycle: one cycle only

Cut: cut the graph into two parts.

Cutset: the edges in the cut

Greedy Algorithm

Blue rule: If there is no blue edge in a cutset, then take any cheapest uncolored edge and color it blue (in this cutset).

Red rule: If there is a simple cycle with no red edges, then take any most expensive uncolored edge in this cycle and color it red.

Algorithm: apply red/blue rules in any order, color all edges until $n-1$ edges are colored blue