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\thmid{mstdef}%
  25 For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
  26 \itemize\ibull
  27 \:A~tree $T$ is a \df{spanning tree} of~$G$ if and only if $V(T)=V(G)$ and $E(T)\subseteq E(G)$.
  28 \:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
  29 \:A~spanning tree~$T$ is \df{minimal} iff $w(T)$ is the smallest possible of all spanning trees.
  30   We use an abbreviation \df{MST} for such trees.
  31 \:For a disconnected graph, a \df{(minimal) spanning forest (MSF)} is defined as
  32   a union of (minimal) spanning trees of its connected components.
  33 \endlist
  34
  35 Bor\accent23uvka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
  36 mostly geometric setting, giving another polynomial algorithm. However, when
  37 computer science and graph theory started forming in the 1950's and the
  38 spanning tree problem was one of the central topics of the flourishing new
  39 disciplines, the previous work was not well known and the algorithms have been
  40 rediscovered several times.
  41
  42 Recently, several significantly faster algorithms were discovered, most notably the
  43 $\O(m\beta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and
  44 algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
  45 and Pettie \cite{pettie:ackermann}.
  46
  47 \FIXME{Write the rest of the history.}
  48
  49 This chapter attempts to survery the important algorithms for finding the MST and it
  50 also presents several new ones.
  51
  52 \section{Basic Properties}
  53
  54 In this section, we will examine the basic properties of spanning trees and prove
  55 several important theorems to base the algorithms upon. We will follow the theory
  56 developed by Tarjan in~\cite{tarjan:dsna}.
  57
  58 For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all other
  59 graphs will be subgraphs of~$G$ containing all of its vertices. We will use the
  60 same notation for the subgraph and for the corresponding set of edges.
  61
  62 First of all, let us show that the weights on edges are not necessary for the
  63 definition of the MST. We can formulate an equivalent characterization using
  64 an ordering of edges instead.
  65
  66 \defnn{Heavy and light edges}\thmid{heavy}%
  67 Let~$T$ be a~spanning tree. Then:
  68 \itemize\ibull
  69 \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
  70 \:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
  71   the edges of this path \df{edges covered by~$e$}.
  72 \:An edge~$e$ is called \df{$T$-light} if it covers a heavier edge, i.e., if there
  73   is an edge $f\in T[e]$ such that $w(f) > w(e)$.
  74 \:An edge~$e$ is called \df{$T$-heavy} if it is not $T$-light.
  75 \endlist
  76
  77 \rem
  78 Please note that the above properties also apply to tree edges
  79 which by definition cover only themselves and therefore they are always heavy.
  80
  81 \lemman{Light edges}\thmid{lightlemma}%
  82 Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
  83 is not minimal.
  84
  85 \proof
  86 If there is a $T$-light edge~$e$, then there exists an edge $f\in T[e]$ such
  87 that $w(f)>w(e)$. Now $T-f$ is a forest of two trees with endpoints of~$e$
  88 located in different components, so adding $e$ to this forest must restore
  89 connectivity and $T':=T-f+e$ is another spanning tree with weight $w(T')
  90 = w(T)-w(f)+w(e) < w(T)$. Hence $T$ could not have been minimal.
  91 \qed
  92
  93 \figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\thmref{lightlemma}}
  94
  95 The converse of this lemma is also true and to prove it, we will once again use
  96 technique of transforming trees by \df{exchanges} of edges. In the proof of the
  97 lemma, we have made use of the fact that whenever we exchange an edge~$e$ of
  98 a spanning tree for another edge~$f$ covered by~$e$, the result is again
  99 a spanning tree. In fact, it is possible to transform any spanning tree
 100 to any other spanning tree by a sequence of exchanges.
 101
 102 \lemman{Exchange property for trees}\thmid{xchglemma}%
 103 Let $T$ and $T'$ be spanning trees of a common graph. Then there exists
 104 a sequence of edge exchanges which transforms $T$ to~$T'$. More formally,
 105 there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that
 106 $T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$.
 107
 108 \proof
 109 By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$, then
 110 both trees are identical and an empty sequence suffices. Otherwise, the trees are different,
 111 but they are of the same size, so there must exist an edge $e'\in T'\setminus T$.
 112 The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must
 113 exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning
 114 tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction
 115 hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
 116 \qed
 117
 118 \figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}}
 119
 120 \lemman{Monotone exchanges}\thmid{monoxchg}%
 121 Let $T$ be a spanning tree such that there are no $T$-light edges and $T$
 122 be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
 123 transforming $T$ to~$T'$ such that the weight does not increase in any step.
 124
 125 \proof
 126 We improve the argument from the previous proof, refining the induction step.
 127 When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$,
 128 the weight never drops, since $e'$ is not a $T$-light edge and therefore
 129 $w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\le w(T)$.
 130
 131 To allow the induction to proceed, we have to make sure that there are still
 132 no light edges with respect to~$T^*$. In fact, it is enough to avoid $T^*$-light
 133 edges in $T'\setminus T^*$, since these are the only edges considered by the
 134 induction step. Instead of picking $e'$ arbitrarily, we will pick the lightest
 135 edge available. Now consider an edge $f\in T'\setminus T^*$. We want to show
 136 that $f$ is heavier than all edges on $T^*[f]$.
 137
 138 The path $T^*[f]$ is either the original path $T[f]$ (if $e\not\in T[f]$)
 139 or $T[f] \symdiff C$, where $C$ is the cycle $T[e']+e$. The first case is
 140 trivial, in the second case $w(f)\ge w(e')$ and all other edges on~$C$
 141 are lighter than~$e'$.
 142 \qed
 143
 144 \theorem
 145 A~spanning tree~$T$ is minimal iff there is no $T$-light edge.
 146
 147 \proof
 148 If~$T$ is minimal, then by Lemma~\thmref{lightlemma} there are no $T$-light
 149 edges.
 150 Conversely, when $T$ is a spanning tree without $T$-light edges
 151 and $T_{min}$ is an arbitrary minimal spanning tree, then according to the Monotone
 152 exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence
 153 of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
 154 and thus $T$~is also minimal.
 155 \qed
 156
 157 In general, a single graph can have many minimal spanning trees (for example
 158 a complete graph on~$n$ vertices and unit edge weights has $n^{n-2}$
 159 minimum spanning trees according to the Cayley's formula \cite{cayley:trees}).
 160 However, this is possible only if the weight function is not injective.
 161
 162 \lemman{MST uniqueness}
 163 If all edge weights are distinct, then the minimum spanning tree is unique.
 164
 165 \proof
 166 Consider two minimal spanning trees $T_1$ and~$T_2$. According to the previous
 167 theorem, there are no light edges with respect to neither of them, so by the
 168 Monotone exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence
 169 of edge exchanges going from $T_1$ to $T_2$. Each exchange in this sequence is
 170 strictly increasing, because all edge weights all distinct. On the other hand,
 171 we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
 172 $T_1$ and $T_2$ must be identical.
 173 \qed
 174
 175 \rem\thmid{edgeoracle}%
 176 To simplify the description of MST algorithms, we will expect that the input
 177 graph has all edge weights distinct. We will also assume that instead of explicit
 178 edge weights we will be given a comparison oracle, that is a function which answers
 179 questions ``$w(e)<w(f)$?'' in constant time. Please note that this is without loss
 180 of generality, because when some edges have identical weights, we can determine their
 181 relative order by comparing some unique identifiers of these edges and every MST
 182 of the new graph will be also a MST of the original one.
 183 In the few cases where we need a more concrete input, we will explicitly say so.
 184
 185 \section{The Red-Blue Meta-Algorithm}
 186
 187 Most MST algorithms can be described as special cases of the following procedure
 188 (again following \cite{tarjan:dsna}):
 189
 190 \algn{Red-Blue Meta-Algorithm}
 191 \algo
 192 \algin A~graph $G$ with an edge comparison oracle (see \thmref{edgeoracle})
 193 \:In the beginning, all edges are colored black.
 194 \:While possible, use one of the following rules:
 195 \::Pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue. \cmt{Blue rule}
 196 \::Pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge red. \cmt{Red rule}
 197 \algout Minimum spanning tree of~$G$ consisting of edges colored blue.
 198 \endalgo
 199
 200 \rem
 201 This is not a proper algorithm, since the selection of rules to apply is not specified.
 202 We will however prove that for any such selection the procedure stops with the correct result.
 203 Also, it will turn out that each of the classical MST algorithms can be stated as a
 204 specific rule selection strategy of this procedure, which justifies the name
 205 meta-algorithm for it.
 206
 207 \lemman{Blue lemma}
 208 When an edge is colored blue in any step of the procedure, it is contained in the minimum spanning tree.
 209
 210 \proof
 211 \qed
 212
 213 \lemman{Red lemma}
 214 When an edge is colored red in any step of the procedure, it is not contained in the minimum spanning tree.
 215
 216 \proof
 217 \qed
 218
 219 \figure{mst-rb.eps}{289pt}{Proof of the Blue (left) and Red (right) lemma}
 220
 221 \lemman{Black lemma}
 222 As long as there exists a black edge, at least one rule can be applied.
 223
 224 \proof
 225 \qed
 226
 227 \figure{mst-bez.eps}{295pt}{Configurations in the proof of the Black lemma}
 228
 229 \theoremn{Red-Blue correctness}
 230 For any selection of rules, the Red-Blue procedure stops and the blue edges form
 231 the minimum spanning tree of the input graph.
 232
 233 \proof
 234 \qed
 235
 236
 237
 238 % mention Steiner trees
 239 % mention matroids
 240 % sorted weights
 241
 242 \endpart