\ifx\endpart\undefined
\input macros.tex
\fi

\chapter{Minimum Spanning Trees}

\section{The Problem}

The problem of finding a minimum spanning tree of a weighted graph is one of the
best studied problems in the area of combinatorial optimization and it can be said
that it stood at the cradle of this discipline. Its colorful history (see \cite{graham:msthistory}
and \cite{nesetril:history} for the full account) begins in~1926 with
the pioneering work of Bor\accent23uvka
\cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
who studied primarily an Euclidean version of the problem related to planning
of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
algorithm for the general version of the problem. As it was well before the birth of graph
theory, the language of his paper was complicated, so we will rather state the problem
in contemporary terminology:

\proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$,
find its minimum spanning tree, where:

\defn For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
\itemize\ibull
\:A~tree $T$ is a \df{spanning tree} of~$G$ if and only if $V(T)=V(G)$ and $E(T)\subseteq E(G)$.
\:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
\:A~spanning tree~$T$ is \df{minimal} iff $w(T)$ is the smallest possible of all spanning trees.
\endlist

Bor\accent23uvka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
mostly geometric setting, giving another polynomial algorithm. However, when
computer science and graph theory started forming in the 1950's and the
spanning tree problem was one of the central topics of the flourishing new
disciplines, the previous work was not well known and the algorithms have been
rediscovered several times.

Recently, several significantly faster algorithms were discovered, most notably the
$\O(m\beta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and
algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
and Pettie \cite{pettie:ackermann}.

\FIXME{Write the rest of the history.}

This chapter attempts to survery the important algorithms for finding the MST and it
also presents several new ones.

\section{Basic Properties}

In this section, we will examine the basic properties of spanning trees and prove
several important theorems to base the algorithms upon. We will follow the theory
developed by Tarjan in~\cite{tarjan:dsna}.

First of all, let us show that the weights on edges are not necessary for the
definition of the MST. We can formulate an equivalent characterization using
an ordering of edges instead.

\defn For a graph~$G$ and its tree subgraph~$T$, we define:
\itemize\ibull
\:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
\:For an edge $e=xy$ outside~$T$, we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
  the edges of this path \df{edges covered by~$e$}.
\:An edge~$e=xy$ outside~$T$ is called \df{$T$-light} if it covers a heavier edge, i.e., if there
  is an edge $f\in T[e]$ such that $w(f) > w(e)$.
\:An edge~$e$ outside~$T$ is called \df{$T$-heavy} if it is not light.
\endlist

\theorem A~spanning tree~$T$ of a graph~$G$ is minimal iff there is no $T$-light edge in~$G$.

To prove this theorem, we will use a notion of edge exchanges, similar to Steinitz theorem
in linear algebra or the exchanges in matroid theory.
\FIXME{reference}

\defn For a tree~$T$ and edges $e\in T$ and $f\not\in T$, the \df{exchange}
XXXXXX

For the other implication, we will make use of the following lemmata, again
based on exchange of edges:

{\narrower
\lemman{Exchange property of spanning trees}
Let $T$ and $T'$ be spanning trees of a common graph~$G$. Then there exists
a sequence

}

Back to the proof of the theorem:

The implication $\Rightarrow$ is straightforward: If there is a $T$-light edge~$e$, there
exists an edge $f\in T[e]$ such that $w(f)>w(e)$. Now $T-f$ is a forest of two trees
with endpoints of~$e$ located in different components, so adding $e$ to this forest
must restore connectivity and $T'=T-f+e$ is another spanning tree with weight $w(T') = w(T)-w(f)+w(e) < w(T)$.
Hence $T$ could not have been minimal.


%\:For a disconnected graph~$G$, we define the \df{(minimal) spanning forest (or MSF)}
%  as an union of (minimal) spanning trees of its connected components.

% mention Steiner trees
% mention matroids
% sorted weights

\endpart
