mst.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \chapter{Minimum Spanning Trees}
   6
   7 \section{The Problem}
   8
   9 The problem of finding a minimum spanning tree of a weighted graph is one of the
  10 best studied problems in the area of combinatorial optimization and it can be said
  11 that it stood at the cradle of this discipline. Its colorful history (see \cite{graham:msthistory}
  12 and \cite{nesetril:history} for the full account) begins in~1926 with
  13 the pioneering work of Bor\accent23uvka
  14 \cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
  15 who studied primarily an Euclidean version of the problem related to planning
  16 of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
  17 algorithm for the general version of the problem. As it was well before the birth of graph
  18 theory, the language of his paper was complicated, so we will rather state the problem
  19 in contemporary terminology:
  20
  21 \proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$,
  22 find its minimum spanning tree, where:
  23
  24 \defn For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
  25 \itemize\ibull
  26 \:A~tree $T$ is a \df{spanning tree} of~$G$ if and only if $V(T)=V(G)$ and $E(T)\subseteq E(G)$.
  27 \:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
  28 \:A~spanning tree~$T$ is \df{minimal} iff $w(T)$ is the smallest possible of all spanning trees.
  29 \endlist
  30
  31 Bor\accent23uvka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
  32 mostly geometric setting, giving another polynomial algorithm. However, when
  33 computer science and graph theory started forming in the 1950's and the
  34 spanning tree problem was one of the central topics of the flourishing new
  35 disciplines, the previous work was not well known and the algorithms have been
  36 rediscovered several times.
  37
  38 Recently, several significantly faster algorithms were discovered, most notably the
  39 $\O(m\beta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and
  40 algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
  41 and Pettie \cite{pettie:ackermann}.
  42
  43 \FIXME{Write the rest of the history.}
  44
  45 This chapter attempts to survery the important algorithms for finding the MST and it
  46 also presents several new ones.
  47
  48 \section{Basic Properties}
  49
  50 In this section, we will examine the basic properties of spanning trees and prove
  51 several important theorems to base the algorithms upon. We will follow the theory
  52 developed by Tarjan in~\cite{tarjan:dsna}.
  53
  54 First of all, let us show that the weights on edges are not necessary for the
  55 definition of the MST. We can formulate an equivalent characterization using
  56 an ordering of edges instead.
  57
  58 \defn For a graph~$G$ and its tree subgraph~$T$, we define:
  59 \itemize\ibull
  60 \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
  61 \:For an edge $e=xy$ outside~$T$, we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
  62   the edges of this path \df{edges covered by~$e$}.
  63 \:An edge~$e=xy$ outside~$T$ is called \df{$T$-light} if it covers a heavier edge, i.e., if there
  64   is an edge $f\in T[e]$ such that $w(f) > w(e)$.
  65 \:An edge~$e$ outside~$T$ is called \df{$T$-heavy} if it is not light.
  66 \endlist
  67
  68 \theorem A~spanning tree~$T$ of a graph~$G$ is minimal iff there is no $T$-light edge in~$G$.
  69
  70 To prove this theorem, we will use a notion of edge exchanges, similar to Steinitz theorem
  71 in linear algebra or the exchanges in matroid theory.
  72 \FIXME{reference}
  73
  74 \defn For a tree~$T$ and edges $e\in T$ and $f\not\in T$, the \df{exchange}
  75 XXXXXX
  76
  77 For the other implication, we will make use of the following lemmata, again
  78 based on exchange of edges:
  79
  80 {\narrower
  81 \lemman{Exchange property of spanning trees}
  82 Let $T$ and $T'$ be spanning trees of a common graph~$G$. Then there exists
  83 a sequence
  84
  85 }
  86
  87 Back to the proof of the theorem:
  88
  89 The implication $\Rightarrow$ is straightforward: If there is a $T$-light edge~$e$, there
  90 exists an edge $f\in T[e]$ such that $w(f)>w(e)$. Now $T-f$ is a forest of two trees
  91 with endpoints of~$e$ located in different components, so adding $e$ to this forest
  92 must restore connectivity and $T'=T-f+e$ is another spanning tree with weight $w(T') = w(T)-w(f)+w(e) < w(T)$.
  93 Hence $T$ could not have been minimal.
  94
  95
  96 %\:For a disconnected graph~$G$, we define the \df{(minimal) spanning forest (or MSF)}
  97 %  as an union of (minimal) spanning trees of its connected components.
  98
  99 % mention Steiner trees
 100 % mention matroids
 101 % sorted weights
 102
 103 \endpart