DMAT_L19

Minimum spanning trees

Definition 1(Definition).

In a connected weighted graph, a minimum spanning tree is a spanning tree with minimum weight.

Kruskal’s algorithm for MSTs

ref

Algorithm

Input: A weighted connected graph.
Idea: Maintain an acyclic subgraph $H$, enlarging it by edges with low weight to form a spanning tree. Consider edges in nondecreasing order of weight, breaking ties arbitrarily.
Initialization: Set $E(H)=\varnothing$.
Iteration: If the next cheapest edge joins two components of $H$, then include it; otherwise, discard it. Terminate when $H$ is connected.

Theorem 2(Theorem).

In a connected weighted graph $G$, Kruskal’s Algorithm constructs a minimum-weight spanning tree.

Proof
It should be clear that the algorithm produces a tree. Let $T$ be the resulting tree, and let $T^{\ast }$ be a spanning tree of minimum weight. If $T=T^{\ast }$, we are done. Else, let $e$ be the first edge chosen for $T$ that is not in $T^{\ast }$. Adding $e$ to $T^{\ast }$ creates one cycle $C$. Since $T$ has no cycle, $C$ has an edge $e^{\prime }\notin E(T)$. Since $T^{\ast }$ contains $e^{\prime }$ and all the edges of $T$ chosen before $e$, both $e^{\prime }$ and $e$ are available when the algorithm choses $e$, and hence $w(e)\le w(e^{\prime })$. Now, consider the spanning tree $T^{\ast }+e-e^{\prime }$, and note that it does not exceed $T^{\ast }$ in weight and agrees with $T$ for a longer list of initial edges than $T^{\ast }$ does. Repeating this argument eventually yields a minimum-weight spanning tree that agrees completely with $T$.

---

A digression: Matroids

ref

Examples of matroids:

• Uniform matroid: all subsets of size $k$
• Linear matroid

Any $e\in \mathcal{I}$ such that $e$ is an element of maximal cardinality is called a base of the matroid.

Graphic matroid: $(E,\mathcal{I})$, where an element in $\mathcal{I}$ is a subset of $E$ containing no cycles.

Exercise 1: Verify that this is a matroid.
Exercise 2: Find a linear representation of a matroid, $i$.$e$, a map from $E$ to ${\mathbb{R}}^k$ for some $k$.