\section{The Problem}
-\cite{boruvka:ojistem}
+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}.
+
+For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all other
+graphs will be subgraphs of~$G$ containing all of its vertices. We will use the
+same notation for the subgraph and for the corresponding set of edges.
+
+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.
+
+\defnn{Heavy and light edges}
+Let~$T$ be a~spanning tree. Then:
+\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$ 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$ 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$ is called \df{$T$-heavy} if it is not $T$-light.
+\endlist
+
+\rem
+Please note that the above properties also apply to tree edges
+which by definition cover only themselves and therefore they are always heavy.
+
+\lemma\thmid{lightlemma}%
+Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
+is not minimal.
+
+\proof
+If there is a $T$-light edge~$e$, then 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.
+\qed
+
+The converse of this lemma is also true and to prove it, we will once again use
+technique of transforming trees by \df{exchanges} of edges. In the proof of the
+lemma, we have made use of the fact that whenever we exchange an edge~$e$ of
+a spanning tree for another edge~$f$ covered by~$e$, the result is again
+a spanning tree. In fact, it is possible to transform any spanning tree
+to any other spanning tree by a sequence of exchanges.
+
+\lemman{Exchange property for trees}
+Let $T$ and $T'$ be spanning trees of a common graph. Then there exists
+a sequence of edge exchanges which transforms $T$ to~$T'$. More formally,
+there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that
+$T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$.
+
+\proof
+By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$, then
+both trees are identical and an empty sequence suffices. Otherwise, the trees are different,
+but they are of the same size, so there must exist an edge $e'\in T'\setminus T$.
+The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must
+exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning
+tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction
+hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
+\qed
+
+\lemman{Monotone exchanges}
+\thmid{monoex}
+Let $T$ be a spanning tree such that there are no $T$-light edges and $T$
+be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
+transforming $T$ to~$T'$ such that the weight does not increase in any step.
+
+\proof
+We improve the argument from the previous proof, refining the induction step.
+When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$,
+the weight never drops, since $e'$ is not a $T$-light edge and therefore
+$w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\le w(T)$.
+
+To allow the induction to proceed, we have to make sure that there are still
+no light edges with respect to~$T^*$. In fact, it is enough to avoid $T^*$-light
+edges in $T'\setminus T^*$, since these are the only edges considered by the
+induction step. Instead of picking $e'$ arbitrarily, we will pick the lightest
+edge available. Now consider an edge $f\in T'\setminus T^*$. We want to show
+that $f$ is heavier than all edges on $T^*[f]$.
+
+The path $T^*[f]$ is either the original path $T[f]$ (if $e\not\in T[f]$)
+or $T[f] \symdiff C$, where $C$ is the cycle $T[e']+e$. The first case is
+trivial, in the second case $w(f)\ge w(e')$ and all other edges on~$C$
+are lighter than~$e'$.
+\qed
+
+\theorem
+A~spanning tree~$T$ is minimal iff there is no $T$-light edge.
+
+\proof
+If~$T$ is minimal, then by Lemma~\thmref{lightlemma} there are no $T$-light
+edges.
+Conversely, when $T$ is a spanning tree without $T$-light edges
+and $T_{min}$ is an arbitrary minimal spanning tree, then according to the Monotone
+exchange lemma~\thmref{monoex} there exists a non-decreasing sequence
+of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
+and thus $T$~is also minimal.
+\qed
% mention Steiner trees
+% mention matroids
+% sorted weights
\endpart
projects / saga.git / blobdiff