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 For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all other
  55 graphs will be subgraphs of~$G$ containing all of its vertices. We will use the
  56 same notation for the subgraph and for the corresponding set of edges.
  57
  58 First of all, let us show that the weights on edges are not necessary for the
  59 definition of the MST. We can formulate an equivalent characterization using
  60 an ordering of edges instead.
  61
  62 \defnn{Heavy and light edges}\thmid{heavy}%
  63 Let~$T$ be a~spanning tree. Then:
  64 \itemize\ibull
  65 \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
  66 \:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
  67   the edges of this path \df{edges covered by~$e$}.
  68 \:An edge~$e$ is called \df{$T$-light} if it covers a heavier edge, i.e., if there
  69   is an edge $f\in T[e]$ such that $w(f) > w(e)$.
  70 \:An edge~$e$ is called \df{$T$-heavy} if it is not $T$-light.
  71 \endlist
  72
  73 \rem
  74 Please note that the above properties also apply to tree edges
  75 which by definition cover only themselves and therefore they are always heavy.
  76
  77 \lemma\thmid{lightlemma}%
  78 Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
  79 is not minimal.
  80
  81 \proof
  82 If there is a $T$-light edge~$e$, then there exists an edge $f\in T[e]$ such
  83 that $w(f)>w(e)$. Now $T-f$ is a forest of two trees with endpoints of~$e$
  84 located in different components, so adding $e$ to this forest must restore
  85 connectivity and $T':=T-f+e$ is another spanning tree with weight $w(T')
  86 = w(T)-w(f)+w(e) < w(T)$. Hence $T$ could not have been minimal.
  87 \qed
  88
  89 \figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\thmref{lightlemma}}
  90
  91 The converse of this lemma is also true and to prove it, we will once again use
  92 technique of transforming trees by \df{exchanges} of edges. In the proof of the
  93 lemma, we have made use of the fact that whenever we exchange an edge~$e$ of
  94 a spanning tree for another edge~$f$ covered by~$e$, the result is again
  95 a spanning tree. In fact, it is possible to transform any spanning tree
  96 to any other spanning tree by a sequence of exchanges.
  97
  98 \lemman{Exchange property for trees}\thmid{xchglemma}%
  99 Let $T$ and $T'$ be spanning trees of a common graph. Then there exists
 100 a sequence of edge exchanges which transforms $T$ to~$T'$. More formally,
 101 there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that
 102 $T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$.
 103
 104 \proof
 105 By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$, then
 106 both trees are identical and an empty sequence suffices. Otherwise, the trees are different,
 107 but they are of the same size, so there must exist an edge $e'\in T'\setminus T$.
 108 The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must
 109 exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning
 110 tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction
 111 hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
 112 \qed
 113
 114 \figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}}
 115
 116 \lemman{Monotone exchanges}\thmid{monoxchg}%
 117 Let $T$ be a spanning tree such that there are no $T$-light edges and $T$
 118 be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
 119 transforming $T$ to~$T'$ such that the weight does not increase in any step.
 120
 121 \proof
 122 We improve the argument from the previous proof, refining the induction step.
 123 When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$,
 124 the weight never drops, since $e'$ is not a $T$-light edge and therefore
 125 $w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\le w(T)$.
 126
 127 To allow the induction to proceed, we have to make sure that there are still
 128 no light edges with respect to~$T^*$. In fact, it is enough to avoid $T^*$-light
 129 edges in $T'\setminus T^*$, since these are the only edges considered by the
 130 induction step. Instead of picking $e'$ arbitrarily, we will pick the lightest
 131 edge available. Now consider an edge $f\in T'\setminus T^*$. We want to show
 132 that $f$ is heavier than all edges on $T^*[f]$.
 133
 134 The path $T^*[f]$ is either the original path $T[f]$ (if $e\not\in T[f]$)
 135 or $T[f] \symdiff C$, where $C$ is the cycle $T[e']+e$. The first case is
 136 trivial, in the second case $w(f)\ge w(e')$ and all other edges on~$C$
 137 are lighter than~$e'$.
 138 \qed
 139
 140 \theorem
 141 A~spanning tree~$T$ is minimal iff there is no $T$-light edge.
 142
 143 \proof
 144 If~$T$ is minimal, then by Lemma~\thmref{lightlemma} there are no $T$-light
 145 edges.
 146 Conversely, when $T$ is a spanning tree without $T$-light edges
 147 and $T_{min}$ is an arbitrary minimal spanning tree, then according to the Monotone
 148 exchange lemma~\thmref{monoxchg} there exists a non-decreasing sequence
 149 of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
 150 and thus $T$~is also minimal.
 151 \qed
 152
 153 % mention Steiner trees
 154 % mention matroids
 155 % sorted weights
 156
 157 \endpart