X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=mst.tex;h=efc4d63238fe433e81007b922e78d9487b477198;hb=3ce379fec86d6348c80aa1d8c77fb64a0dbada13;hp=2a562dbbcb255d3db844bb7c09359624af24c7f3;hpb=27749502e55ddcb33010db5294e13f0ff2728668;p=saga.git

diff --git a/mst.tex b/mst.tex
index 2a562db..efc4d63 100644
--- a/mst.tex
+++ b/mst.tex
@@ -24,7 +24,7 @@ find its minimum spanning tree, defined as follows:
 For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
 \itemize\ibull
 \:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$.
-\:A~\df{spanning tree} of $G$ is any its spanning subgraph which is a tree.
+\:A~\df{spanning tree} of~$G$ is any spanning subgraph of~$G$ that is a tree.
 \:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
   When comparing two weights, we will use the terms \df{lighter} and \df{heavier} in the
   obvious sense.
@@ -41,25 +41,27 @@ spanning tree problem was one of the central topics of the flourishing new
 disciplines, the previous work was not well known and the algorithms had to be
 rediscovered several times.
 
-Recently, several significantly faster algorithms were discovered, most notably the
-$\O(m\timesbeta(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}.
+In the next 50 years, several significantly faster algorithms were discovered, ranging
+from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci},
+over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
+and Pettie \cite{pettie:ackermann}, to another algorithm by Pettie \cite{pettie:optimal}
+whose time complexity is provably optimal.
 
-\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.
+In the upcoming chapters, we will explore this colorful universe of MST algorithms.
+We will meet the canonical works of the classics, the clever ideas of their successors,
+various approaches to the problem including randomization and solving of important
+special cases. At several places, we will try to contribute our little stones to this
+mosaic.
 
 %--------------------------------------------------------------------------------
 
-\section{Basic properties}
+\section{Basic properties}\id{mstbasics}%
 
 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}.
+several important theorems which will serve as a~foundation for our MST algorithms.
+We will mostly 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
+For the whole section, we will fix a~connected graph~$G$ with edge weights~$w$ and all
 other graphs will be spanning subgraphs of~$G$. We will use the same notation
 for the subgraphs as for the corresponding sets of edges.
 
@@ -75,12 +77,13 @@ Let~$T$ be a~spanning tree. Then:
   the edges of this path \df{edges covered by~$e$}.
 \:An edge~$e$ is called \df{light with respect to~$T$} (or just \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.
+\:An edge~$e$ is called \df{$T$-heavy} if it covers a~lighter edge.
 \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.
+Edges of the tree~$T$ cover only themselves and thus they are neither heavy nor light.
+The same can happen if an~edge outside~$T$ covers only edges of the same weight,
+but this will be rare because all edge weights will be usually distinct.
 
 \lemman{Light edges}\id{lightlemma}%
 Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
@@ -105,7 +108,7 @@ to any other spanning tree by a sequence of exchanges.
 
 \lemman{Exchange property for trees}\id{xchglemma}%
 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,
+a sequence of edge exchanges that 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'$.
 
@@ -124,7 +127,7 @@ hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence.
 \lemman{Monotone exchanges}\id{monoxchg}%
 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.
+transforming $T$ to~$T'$ such that the weight does not decrease in any step.
 
 \proof
 We improve the argument from the previous proof, refining the induction step.
@@ -146,7 +149,7 @@ $w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter
 than~$e'$ as $e'$ was not $T$-light.
 \qed
 
-\thmn{Minimality by order}\id{mstthm}%
+\thmn{Minimality of spanning trees}\id{mstthm}%
 A~spanning tree~$T$ is minimum iff there is no $T$-light edge.
 
 \proof
@@ -165,7 +168,7 @@ minimum spanning trees according to the Cayley's formula \cite{cayley:trees}).
 However, as the following theorem shows, this is possible only if the weight
 function is not injective.
 
-\thmn{MST uniqueness}%
+\thmn{Uniqueness of MST}%
 If all edge weights are distinct, then the minimum spanning tree is unique.
 
 \proof
@@ -178,41 +181,58 @@ we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
 $T_1$ and $T_2$ must be identical.
 \qed
 
-\rem\id{edgeoracle}%
-To simplify the description of MST algorithms, we will expect that the weights
-of all edges are distinct and that instead of numeric weights (usually accompanied
-by problems with representation of real numbers in algorithms) we will be given
-a comparison oracle, that is a function which answers questions ``$w(e)<w(f)$?'' in
-constant time. In case the weights are not distinct, we can easily break ties by
-comparing some unique edge identifiers and according to our characterization of
-minimum spanning trees, the unique MST of the new graph will still be a MST of the
-original graph. In the few cases where we need a more concrete input, we will
-explicitly state so.
-
 \nota\id{mstnota}%
 When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
 its unique minimum spanning tree.
 
+The following trivial lemma will be often invaluable:
+
+\lemman{Edge removal}
+Let~$G$ be a~graph with distinct edge weights and $e$ any its edge
+which does not lie in~$\mst(G)$. Then $\mst(G-e) = \mst(G)$.
+
+\proof
+The tree $T=\mst(G)$ is also a~MST of~$G-e$, because every $T$-light
+edge in~$G-e$ is also $T$-light in~$G$. Then we apply the uniqueness of
+the MST of~$G-e$.
+\qed
+
+\paran{Comparison oracles}\id{edgeoracle}%
+To simplify the description of MST algorithms, we will assume that the weights
+of all edges are distinct and that instead of numeric weights we are given a~comparison oracle.
+The oracle is a~function that answers questions of type ``Is $w(e)<w(f)$?'' in
+constant time. This will conveniently shield us from problems with representation
+of real numbers in algorithms and in the few cases where we need a more concrete
+input, we will explicitly state so.
+
+In case the weights are not distinct, we can easily break ties by comparing some
+unique identifiers of edges. According to our characterization of minimum spanning
+trees, the unique MST of the new graph will still be a~MST of the original graph.
+
+\obs
+If all edge weights are distinct and $T$~is an~arbitrary tree, then for every tree~$T$ all edges are
+either $T$-heavy, or $T$-light, or contained in~$T$.
+
+\paran{Monotone isomorphism}%
 Another useful consequence is that whenever two graphs are isomorphic and the
-isomorphism preserves weight order, the isomorphism applies to their MST's
-as well:
+isomorphism preserves the relative order of weights, the isomorphism applies to their MST's as well:
 
 \defn
-A~\df{monotone isomorphism} of two weighted graphs $G_1=(V_1,E_1,w_1)$ and
+A~\df{monotone isomorphism} between two weighted graphs $G_1=(V_1,E_1,w_1)$ and
 $G_2=(V_2,E_2,w_2)$ is a bijection $\pi: V_1\rightarrow V_2$ such that
 for each $u,v\in V_1: uv\in E_1 \Leftrightarrow \pi(u)\pi(v)\in E_2$ and
 for each $e,f\in E_1: w_1(e)<w_1(f) \Leftrightarrow w_2(\pi[e]) < w_2(\pi[f])$.
 
 \lemman{MST of isomorphic graphs}\id{mstiso}%
-Let~$G_1$ and $G_2$ be two weighted graphs with unique edge weights and $\pi$
-their monotone isomorphism. Then $\mst(G_2) = \pi[\mst(G_1)]$.
+Let~$G_1$ and $G_2$ be two weighted graphs with distinct edge weights and $\pi$
+a~monotone isomorphism between them. Then $\mst(G_2) = \pi[\mst(G_1)]$.
 
 \proof
 The isomorphism~$\pi$ maps spanning trees onto spanning trees and it preserves
 the relation of covering. Since it is monotone, it preserves the property of
 being a light edge (an~edge $e\in E(G_1)$ is $T$-light $\Leftrightarrow$
-the edge $\pi[e]\in E(G_2)$ is~$f[T]$-light). Therefore by Theorem~\ref{mstthm}, $T$
-is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$.
+the edge $\pi[e]\in E(G_2)$ is~$f[T]$-light). Therefore by the Minimality Theorem
+(\ref{mstthm}), $T$ is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$.
 \qed
 
 %--------------------------------------------------------------------------------
@@ -220,7 +240,7 @@ is the MST of~$G_1$ if and only if $\pi[T]$ is the MST of~$G_2$.
 \section{The Red-Blue meta-algorithm}
 
 Most MST algorithms can be described as special cases of the following procedure
-(again following \cite{tarjan:dsna}):
+(again following Tarjan \cite{tarjan:dsna}):
 
 \algn{Red-Blue Meta-Algorithm}\id{rbma}%
 \algo
@@ -228,11 +248,11 @@ Most MST algorithms can be described as special cases of the following procedure
 \:In the beginning, all edges are colored black.
 \:Apply rules as long as possible:
 \::Either pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue, \cmt{Blue rule}
-\::Or pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge \rack{blue.}{red.} \cmt{Red rule}
+\::or pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge \rack{blue.}{red.\hfil} \cmt{Red rule}
 \algout Minimum spanning tree of~$G$ consisting of edges colored blue.
 \endalgo
 
-\rem
+\para
 This procedure is not a proper algorithm, since it does not specify how to choose
 the rule to apply. We will however prove that no matter how the rules are applied,
 the procedure always stops and gives the correct result. Also, it will turn out
@@ -243,27 +263,39 @@ of choosing the rules in this procedure, which justifies the name meta-algorithm
 We will denote the unique minimum spanning tree of the input graph by~$T_{min}$.
 We intend to prove that this is also the output of the procedure.
 
-\lemman{Blue lemma}%
-When an edge is colored blue in any step of the procedure, it is contained in the minimum spanning tree.
+\paran{Correctness}%
+Let us prove that the meta-algorithm is correct. First we show that the edges colored
+blue in any step of the procedure always belong to~$T_{min}$ and that edges colored
+red are guaranteed to be outside~$T_{min}$. Then we demonstrate that the procedure
+always stops. We will prefer a~slightly more general formulation of the lemmata, which will turn out
+to be useful in the future chapters.
+
+\lemman{Blue lemma, also known as the Cut rule}\id{bluelemma}%
+The lightest edge of every cut is contained in the MST.
 
 \proof
-By contradiction. Let $e$ be an edge painted blue as the lightest edge of a cut~$C$.
-If $e\not\in T_{min}$, then there must exist an edge $e'\in T_{min}$ which is
-contained in~$C$ (take any pair of vertices separated by~$C$, the path
+By contradiction. Let $e$ be the lightest edge of a cut~$C$.
+If $e\not\in T_{min}$, then there must exist an edge $e'\in T_{min}$ that is
+contained in~$C$ (take any pair of vertices separated by~$C$: the path
 in~$T_{min}$ joining these vertices must cross~$C$ at least once). Exchanging
 $e$ for $e'$ in $T_{min}$ yields an even lighter spanning tree since
-$w(e)<w(e')$. \qed
+$w(e)<w(e')$.
+\qed
 
-\lemman{Red lemma}%
-When an edge is colored red in any step of the procedure, it is not contained in the minimum spanning tree.
+\lemman{Red lemma, also known as the Cycle rule}\id{redlemma}%
+An~edge~$e$ is not contained in the MST iff it is the heaviest on some cycle.
 
 \proof
-Again by contradiction. Suppose that $e$ is an edge painted red as the heaviest edge
-of a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split to two
-components, let us call them $T_x$ and $T_y$. Some vertices of~$C$ now lie in $T_x$,
-the others in $T_y$, so there must exist in edge $e'\ne e$ such that its endpoints
-lie in different components. Since $w(e')<w(e)$, exchanging $e$ for~$e'$ yields
-a lighter spanning tree than $T_{min}$.
+The implication from the left to the right follows directly from the Minimality
+theorem: if~$e\not\in T_{min}$, then $e$~is $T_{min}$-heavy and so it is the heaviest
+edge on the cycle $T_{min}[e]+e$.
+
+We will prove the other implication again by contradiction. Suppose that $e$ is the heaviest edge of
+a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split
+to two components, let us call them $T_x$ and~$T_y$. Some vertices of~$C$ now lie in~$T_x$, the
+others in~$T_y$, so there must exist in edge $e'\ne e$ such that its endpoints lie in different
+components. Since $w(e')<w(e)$, exchanging $e$ for~$e'$ yields a~spanning tree lighter than
+$T_{min}$.
 \qed
 
 \figure{mst-rb.eps}{289pt}{Proof of the Blue (left) and Red (right) lemma}
@@ -277,10 +309,10 @@ reachable from~$x$ using only blue edges. If $y$~lies in~$M$, then $e$ together
 with some blue path between $x$ and $y$ forms a cycle and it must be the heaviest
 edge on this cycle. This holds because all blue edges have been already proven
 to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\ref{mstthm}).
-In this case we can apply the red rule.
+In this case we can apply the Red rule.
 
 On the other hand, if $y\not\in M$, then the cut formed by all edges between $M$
-and $V(G)\setminus M$ contains no blue edges, therefore we can use the blue rule.
+and $V(G)\setminus M$ contains no blue edges, therefore we can use the Blue rule.
 \qed
 
 \figure{mst-bez.eps}{295pt}{Configurations in the proof of the Black lemma}
@@ -293,7 +325,7 @@ the minimum spanning tree of the input graph.
 To prove that the procedure stops, let us notice that no edge is ever recolored,
 so we must run out of black edges after at most~$m$ steps. Recoloring
 to the same color is avoided by the conditions built in the rules, recoloring to
-a different color would mean that the an edge would be both inside and outside~$T_{min}$
+a different color would mean that the edge would be both inside and outside~$T_{min}$
 due to our Red and Blue lemmata.
 
 When no further rules can be applied, the Black lemma guarantees that all edges
@@ -301,15 +333,32 @@ are colored, so by the Blue lemma all blue edges are in~$T_{min}$ and by the Red
 lemma all other (red) edges are outside~$T_{min}$, so the blue edges are exactly~$T_{min}$.
 \qed
 
+\rem
+The MST problem is a~special case of the problem of finding the minimum basis
+of a~weighted matroid. Surprisingly, when we modify the Red-Blue procedure to
+use the standard definitions of cycles and cuts in matroids, it will always
+find the minimum basis. Some of the other MST algorithms also easily generalize to
+matroids and in some sense matroids are exactly the objects where ``the greedy approach works''. We
+will however not pursue this direction in our work, referring the reader to the Oxley's monograph
+\cite{oxley:matroids} instead.
+
 %--------------------------------------------------------------------------------
 
-\section{Classical algorithms}
+\section{Classical algorithms}\id{classalg}%
 
 The three classical MST algorithms can be easily stated in terms of the Red-Blue meta-algorithm.
 For each of them, we first show the general version of the algorithm, then we prove that
 it gives the correct result and finally we discuss the time complexity of various
 implementations.
 
+\paran{Bor\o{u}vka's algorithm}%
+The oldest MST algorithm is based on a~simple idea: grow a~forest in a~sequence of
+iterations until it becomes connected. We start with a~forest of isolated
+vertices. In each iteration, we let each tree of the forest select the lightest
+edge of those having exactly one endpoint in the tree (we will call such edges
+the \df{neighboring edges} of the tree). We add all such edges to the forest and
+proceed with the next iteration.
+
 \algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst} and others}
 \algo
 \algin A~graph~$G$ with an edge comparison oracle.
@@ -332,7 +381,7 @@ contains two or more original trees.
 \cor
 The algorithm stops in $\O(\log n)$ iterations.
 
-\lemma
+\lemma\id{borcorr}%
 Bor\o{u}vka's algorithm outputs the MST of the input graph.
 
 \proof
@@ -343,7 +392,8 @@ we do not need the Red rule to explicitly exclude edges.
 
 It remains to show that adding the edges simultaneously does not
 produce a cycle. Consider the first iteration of the algorithm where $T$ contains a~cycle~$C$. Without
-loss of generality we can assume that $C=T_1[u_1v_1]\,v_1u_2\,T_2[u_2v_2]\,v_2u_3\,T_3[u_3v_3]\, \ldots \,T_k[u_kv_k]\,v_ku_1$.
+loss of generality we can assume that:
+$$C=T_1[u_1v_1]\,v_1u_2\,T_2[u_2v_2]\,v_2u_3\,T_3[u_3v_3]\, \ldots \,T_k[u_kv_k]\,v_ku_1.$$
 Each component $T_i$ has chosen its lightest incident edge~$e_i$ as either the edge $v_iu_{i+1}$
 or $v_{i-1}u_i$ (indexing cyclically). Suppose that $e_1=v_1u_2$ (otherwise we reverse the orientation
 of the cycle). Then $e_2=v_2u_3$ and $w(e_2)<w(e_1)$ and we can continue in the same way,
@@ -359,7 +409,7 @@ We assign a label to each tree and we keep a mapping from vertices to the
 labels of the trees they belong to. We scan all edges, map their endpoints
 to the particular trees and for each tree we maintain the lightest incident edge
 so far encountered. Instead of merging the trees one by one (which would be too
-slow), we build an auxilliary graph whose vertices are the labels of the original
+slow), we build an auxiliary graph whose vertices are the labels of the original
 trees and edges correspond to the chosen lightest inter-tree edges. We find connected
 components of this graph, these determine how are the original labels translated
 to the new labels.
@@ -372,6 +422,12 @@ Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
 Follows from the previous lemmata.
 \qed
 
+\paran{Jarn\'\i{}k's algorithm}%
+The next algorithm, discovered independently by Jarn\'\i{}k, Prim and Dijkstra, is similar
+to Bor\o{u}vka's algorithm, but instead of the whole forest it concentrates on
+a~single tree. It starts with a~single vertex and it repeatedly extends the tree
+by the lightest neighboring edge until it spans the whole graph.
+
 \algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}\id{jarnik}%
 \algo
 \algin A~graph~$G$ with an edge comparison oracle.
@@ -383,7 +439,7 @@ Follows from the previous lemmata.
 \endalgo
 
 \lemma
-Jarn\'\i{}k's algorithm computers the MST of the input graph.
+Jarn\'\i{}k's algorithm computes the MST of the input graph.
 
 \proof
 If~$G$ is connected, the algorithm always stops. Let us prove that in every step of
@@ -393,31 +449,37 @@ the remaining edges, since for a connected graph the algorithm always stops with
 number of blue edges.
 \qed
 
-\impl
-The most important part of the algorithm is finding \em{neighboring edges,} i.e., edges
-of the cut $\delta(T)$. In a~straightforward implementation,
-searching for the lightest neighboring edge takes $\Theta(m)$ time, so the whole
-algorithm runs in time $\Theta(mn)$.
+\impl\id{jarnimpl}%
+The most important part of the algorithm is finding \em{neighboring edges.}
+In a~straightforward implementation, searching for the lightest neighboring
+edge takes $\Theta(m)$ time, so the whole algorithm runs in time $\Theta(mn)$.
 
 We can do much better by using a binary
 heap to hold all neighboring edges. In each iteration, we find and delete the
 minimum edge from the heap and once we expand the tree, we insert the newly discovered
-neighboring edges to the heap while deleting the neighboring edges which become
+neighboring edges to the heap while deleting the neighboring edges that become
 internal to the new tree. Since there are always at most~$m$ edges in the heap,
 each heap operation takes $\O(\log m)=\O(\log n)$ time. For every edge, we perform
 at most one insertion and at most one deletion, so we spend $\O(m\log n)$ time in total.
 From this, we can conclude:
 
 \thm
-Jarn\'\i{}k's algorithm finds the MST of a~given graph in time $\O(m\log n)$.
+Jarn\'\i{}k's algorithm computes the MST of a~given graph in time $\O(m\log n)$.
 
 \rem
-We will show several faster implementations in section \ref{fibonacci}.
+We will show several faster implementations in section \ref{iteralg}.
 
-\algn{Kruskal \cite{kruskal:mst}, the Greedy algorithm}
+\paran{Kruskal's algorithm}%
+The last of the three classical algorithms processes the edges of the
+graph~$G$ greedily. It starts with an~empty forest and it takes the edges of~$G$
+in order of their increasing weights. For every edge, it checks whether its
+addition to the forest produces a~cycle and if it does not, the edge is added.
+Otherwise, the edge is dropped and not considered again.
+
+\algn{Kruskal \cite{kruskal:mst}}
 \algo
 \algin A~graph~$G$ with an edge comparison oracle.
-\:Sort edges of~$G$ by their increasing weight.
+\:Sort edges of~$G$ by their increasing weights.
 \:$T\=\emptyset$. \cmt{an empty spanning subgraph}
 \:For all edges $e$ in their sorted order:
 \::If $T+e$ is acyclic, add~$e$ to~$T$.
@@ -438,38 +500,55 @@ so~$T$ must be the~MST.
 \qed
 
 \impl
-Except for the initial sorting, which in general takes $\Theta(m\log m)$ time, the only
-other non-trivial operation is the detection of cycles. What we need is a data structure
+Except for the initial sorting, which in general requires $\Theta(m\log m)$ time, the only
+other non-trivial operation is the detection of cycles. What we need is a~data structure
 for maintaining connected components, which supports queries and edge insertion.
-(This is also known under the name Disjoint Set Union problem, i.e., maintenance
-of an~equivalence relation on a~set with queries on whether two elements are equivalent
-and the operation of joining two equivalence classes into one.)
-The following theorem shows that it can be done with surprising efficiency.
+This is closely related to the well-known Disjoint Set Union problem:
+
+\problemn{Disjoint Set Union (DSU)}
+Maintain an~equivalence relation on a~finite set under a~sequence of operations \<Union>
+and \<Find>. The \<Find> operation tests whether two elements are equivalent and \<Union>
+joins two different equivalence classes into one.
 
-\thmn{Incremental connectivity}%
-When only edge insertions and connectivity queries are allowed, connected components
-can be maintained in $\O(\alpha(n))$ time amortized per operation.
+\para
+We can maintain the connected components of our forest~$T$ as equivalence classes. When we want
+to add an~edge~$uv$, we first call $\<Find>(u,v)$ to check if both endpoints of the edge lie in
+the same components. If they do not, addition of this edge connects both components into one,
+so we perform $\<Union>(u,v)$ to merge the equivalence classes.
+
+Tarjan and van Leeuwen have shown that there is a~data structure for the DSU problem
+with surprising efficiency:
+
+\thmn{Disjoint Set Union, Tarjan and van Leeuwen \cite{tarjan:setunion}}\id{dfu}%
+Starting with a~trivial equivalence with single-element classes, a~sequence of operations
+comprising of $n$~\<Union>s intermixed with $m\ge n$~\<Find>s can be processed in time
+$\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's function
+(see Definition \ref{ackerinv}).
 
 \proof
-Proven by Tarjan and van Leeuwen in \cite{tarjan:setunion}.
+See \cite{tarjan:setunion}.
 \qed
 
-\FIXME{Define Ackermann's function. Use $\alpha(m,n)$?}
+This completes the following theorem:
+
+\thm\id{kruskal}%
+Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$.
+If the edges are already sorted by their weights, the time drops to
+$\O(m\timesalpha(m,n))$.
+
+\proof
+We spend $\O(m\log n)$ on sorting, $\O(m\timesalpha(m,n))$ on processing the sequence
+of \<Union>s and \<Find>s, and $\O(m)$ on all other work.
+\qed
 
 \rem
-The cost of the operations on components is of course dwarfed by the complexity
+The cost of the \<Union> and \<Find> operations is of course dwarfed by the complexity
 of sorting, so a much simpler (at least in terms of its analysis) data
 structure would be sufficient, as long as it has $\O(\log n)$ amortized complexity
 per operation. For example, we can label vertices with identifiers of the
-corresponding components and always recolor the smaller of the two components.
-
-\thm
-Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$
-or $\O(m\timesalpha(n))$ if the edges are already sorted by their weights.
+corresponding components and always relabel the smaller of the two components.
 
-\proof
-Follows from the above analysis.
-\qed
+We will study dynamic maintenance of connected components in more detail in Chapter~\ref{dynchap}.
 
 %--------------------------------------------------------------------------------
 
@@ -477,7 +556,7 @@ Follows from the above analysis.
 
 While the classical algorithms are based on growing suitable trees, they
 can be also reformulated in terms of edge contraction. Instead of keeping
-a forest of trees, we can keep each tree contracted to a single vertex.
+a~forest of trees, we can keep each tree contracted to a single vertex.
 This replaces the relatively complex tree-edge incidencies by simple
 vertex-edge incidencies, potentially speeding up the calculation at the
 expense of having to perform the contractions.
@@ -486,8 +565,8 @@ We will show a contractive version of the Bor\o{u}vka's algorithm
 in which these costs are carefully balanced, leading for example to
 a linear-time algorithm for MST in planar graphs.
 
-There are two definitions of edge contraction which differ when an edge of a
-triangle is contracted. Either we unify the other two edges to a single edge
+There are two definitions of edge contraction that differ when an edge of
+a~triangle is contracted. Either we unify the other two edges to a single edge
 or we keep them as two parallel edges, leaving us with a~multigraph. We will
 use the multigraph version and we will show that we can easily reduce the multigraph
 to a simple graph later. (See \ref{contract} for the exact definitions.)
@@ -504,14 +583,10 @@ Then $G'$~has the same MST as~$G$.
 \proof
 Every spanning tree of~$G'$ is a spanning tree of~$G$. In the other direction:
 Loops can be never contained in a spanning tree. If there is a spanning tree~$T$
-containing a removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$
-for~$e$ makes~$T$ lighter. \qed
-
-\rem Removal of the heavier of a pair of parallel edges can be also viewed
-as an application of the Red rule on a two-edge cycle. And indeed it is, the
-Red-Blue procedure works on multigraphs as well as on simple graphs and all the
-classical algorithms also do. We would only have to be more careful in the
-formulations and proofs, which we preferred to avoid.
+containing a~removed edge~$e$ parallel to an edge~$e'\in G'$, exchanging $e'$
+for~$e$ makes~$T$ lighter. (This is indeed the multigraph version of the Red
+lemma applied to a~two-edge cycle, as we will see in \ref{multimst}.)
+\qed
 
 \algn{Contractive version of Bor\o{u}vka's algorithm}\id{contbor}
 \algo
@@ -519,58 +594,63 @@ formulations and proofs, which we preferred to avoid.
 \:$T\=\emptyset$.
 \:$\ell(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.}
 \:While $n(G)>1$:
-\::For each vertex $v_i$ of~$G$, let $e_i$ be the lightest edge incident to~$v_i$.
-\::$T\=T\cup \{ \ell(e_i) \}$. \cmt{Remember labels of all selected edges.}
-\::Contract $G$ along all edges $e_i$, inheriting labels and weights.\foot{In other words, we ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.}
+\::For each vertex $v_k$ of~$G$, let $e_k$ be the lightest edge incident to~$v_k$.
+\::$T\=T\cup \{ \ell(e_k) \}$. \cmt{Remember labels of all selected edges.}
+\::Contract all edges $e_k$, inheriting labels and weights.\foot{In other words, we ask the comparison oracle for the edge $\ell(e)$ instead of~$e$.}
 \::Flatten $G$, removing parallel edges and loops.
 \algout Minimum spanning tree~$T$.
 \endalgo
 
+\nota
+For the analysis of the algorithm, we will denote the graph considered by the algorithm
+at the beginning of the $i$-th iteration by $G_i$ (starting with $G_0=G$) and the number
+of vertices and edges of this graph by $n_i$ and $m_i$ respectively.
+
 \lemma\id{contiter}%
-Each iteration of the algorithm can be carried out in time~$\O(m)$.
+The $i$-th iteration of the algorithm (also called the \df{Bor\o{u}vka step}) can be carried
+out in time~$\O(m_i)$.
 
 \proof
 The only non-trivial parts are steps 6 and~7. Contractions can be handled similarly
 to the unions in the original Bor\o{u}vka's algorithm (see \ref{boruvkaiter}):
-We build an auxillary graph containing only the selected edges~$e_i$, find
+We build an auxiliary graph containing only the selected edges~$e_k$, find
 connected components of this graph and renumber vertices in each component to
-the identifier of the component. This takes $\O(m)$ time.
+the identifier of the component. This takes $\O(m_i)$ time.
 
 Flattening is performed by first removing the loops and then bucket-sorting the edges
 (as ordered pairs of vertex identifiers) lexicographically, which brings parallel
-edges together. The bucket sort uses two passes with $n$~buckets, so it takes
-$\O(n+m)=\O(m)$.
+edges together. The bucket sort uses two passes with $n_i$~buckets, so it takes
+$\O(n_i+m_i)=\O(m_i)$.
 \qed
 
-\thm
-The Contractive Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
+\thm\id{contborthm}%
+The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in
+time $\O(\min(n^2,m\log n))$.
 
 \proof
 As in the original Bor\o{u}vka's algorithm, the number of iterations is $\O(\log n)$.
-Then apply the previous lemma.
+When combined with the previous lemma, it gives an~$\O(m\log n)$ upper bound.
+
+To get the $\O(n^2)$ bound, we observe that the number of trees in the non-contracting
+version of the algorithm drops at least by a factor of two in each iteration (Lemma \ref{boruvkadrop})
+and the same must hold for the number of vertices in the contracting version.
+Therefore $n_i\le n/2^i$. While the number of edges need not decrease geometrically,
+we still have $m_i\le n_i^2$ as the graphs~$G_i$ are simple (we explicitly removed multiple
+edges and loops at the end of the previous iteration). Hence the total time spent
+in all iterations is $\O(\sum_i n_i^2) = \O(\sum_i n^2/4^i) = \O(n^2)$.
 \qed
 
-\thmn{\cite{mm:mst}}\id{planarbor}%
+\thmn{Contractive Bor\o{u}vka on planar graphs, \cite{mm:mst}}\id{planarbor}%
 When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
 time $\O(n)$.
 
 \proof
-Let us denote the graph considered by the algorithm at the beginning of the $i$-th
-iteration by $G_i$ (starting with $G_0=G$) and its number of vertices and edges
-by $n_i$ and $m_i$ respectively. As we already know from the previous lemma,
-the $i$-th iteration takes $\O(m_i)$ time. We are going to prove that the
-$m_i$'s are decreasing geometrically.
-
-The number of trees in the non-contracting version of the algorithm drops
-at least by a factor of two in each iteration (Lemma \ref{boruvkadrop}) and the
-same must hold for the number of vertices in the contracting version.
-Therefore $n_i\le n/2^i$.
-
-However, every $G_i$ is planar, because the class of planar graphs is closed
-under edge deletion and contraction. The~$G_i$ is also simple as we explicitly removed multiple edges and
-loops at the end of the previous iteration. Hence we can use the standard theorem on
+Let us refine the previous proof. We already know that $n_i \le n/2^i$. We will
+prove that when~$G$ is planar, the $m_i$'s are decreasing geometrically. We know that every
+$G_i$ is planar, because the class of planar graphs is closed under edge deletion and
+contraction. Moreover, $G_i$~is also simple, so we can use the standard theorem on
 the number of edges of planar simple graphs (see for example \cite{diestel:gt}) to get $m_i\le 3n_i \le 3n/2^i$.
-From this we get that the total time complexity is $\O(\sum_i m_i)=\O(\sum_i n/2^i)=\O(n)$.
+The total time complexity of the algorithm is therefore $\O(\sum_i m_i)=\O(\sum_i n/2^i)=\O(n)$.
 \qed
 
 \rem
@@ -584,13 +664,13 @@ in section~\ref{minorclosed}.
 To achieve the linear time complexity, the algorithm needs a very careful implementation,
 but we defer the technical details to section~\ref{bucketsort}.
 
-\para
+\paran{General contractions}%
 Graph contractions are indeed a~very powerful tool and they can be used in other MST
 algorithms as well. The following lemma shows the gist:
 
 \lemman{Contraction of MST edges}\id{contlemma}%
 Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
-produced by contracting $G$ along~$e$, and $\pi$ the bijection between edges of~$G-e$ and
+produced by contracting~$e$ in~$G$, and $\pi$ the bijection between edges of~$G-e$ and
 their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$
 
 \proof
@@ -611,10 +691,11 @@ which obviously works in multigraphs as well.)
 \rem
 In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$.
 
-Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity
+\paran{A~lower bound}%
+Finally, we will show a family of graphs for which the $\O(m\log n)$ bound on time complexity
 is tight. The graphs do not have unique weights, but they are constructed in a way that
 the algorithm never compares two edges with the same weight. Therefore, when two such
-graphs are monotonely isomorphic (see~\ref{mstiso}), the algorithm processes them in the same way.
+graphs are monotonically isomorphic (see~\ref{mstiso}), the algorithm processes them in the same way.
 
 \defn
 A~\df{distractor of order~$k$,} denoted by~$D_k$, is a path on $n=2^k$~vertices $v_1,\ldots,v_n$
@@ -668,4 +749,55 @@ to finish on the remaining complete graph. Each iteration runs on a graph with $
 edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices.
 \qed
 
+%--------------------------------------------------------------------------------
+
+\section{Lifting restrictions}
+
+In order to have a~simple and neat theory, we have introduced several restrictions
+on the graphs in which we search for the MST. As in some rare cases we are going to
+meet graphs that do not fit into this simplified world, let us quickly examine what
+happens when the restrictions are lifted.
+
+\paran{Disconnected graphs}\id{disconn}%
+The basic properties of minimum spanning trees and the algorithms presented in
+this chapter apply to minimum spanning forests of disconnected graphs, too.
+The proofs of our theorems and the steps of our algorithms are based on adjacency
+of vertices and existence of paths, so they are always local to a~single
+connected component. The Bor\o{u}vka's and Kruskal's algorithm need no changes,
+the Jarn\'\i{}k's algorithm has to be invoked separately for each component.
+
+We can also extend the notion of light and heavy edges with respect
+to a~tree to forests: When an~edge~$e$ connects two vertices lying in the same
+tree~$T$ of a~forest~$F$, it is $F$-heavy iff it is $T$-heavy (similarly
+for $F$-light). Edges connecting two different trees are always considered
+$F$-light. Again, a~spanning forest~$F$ is minimum iff there are no $F$-light
+edges.
+
+\paran{Multigraphs}\id{multimst}%
+All theorems and algorithms from this chapter work for multigraphs as well,
+only the notation sometimes gets crabbed, which we preferred to avoid. The Minimality
+theorem and the Blue rule stay unchanged. The Red rule is naturally extended to
+self-loops (which are never in the MST) and two-edge cycles (where the heavier
+edge can be dropped) as already suggested in the Flattening lemma (\ref{flattening}).
+
+\paran{Multiple edges of the same weight}\id{multiweight}%
+In case when the edge weights are not distinct, the characterization of minimum
+spanning trees using light edges is still correct, but the MST is no longer unique
+(as already mentioned, there can be as much as~$n^{n-2}$ MST's).
+
+In the Red-Blue procedure, we have to avoid being too zealous. The Blue lemma cannot
+guarantee that when a~cut contains multiple edges of the minimum weight, all of them
+are in the MST. It will however tell that if we pick one of these edges, an~arbitrary
+MST can be modified to another MST that contains this edge. Therefore the Blue rule
+will change to ``Pick a~cut~$C$ such that it does not contain any blue edge and color
+one of its lightest edges blue.'' The Red lemma and the Red rule can be handled
+in a~similar manner. The modified algorithm will be then guaranteed to find one of
+the possible MST's.
+
+The Kruskal's and Jarn\'\i{}k's algorithms keep working. This is however not the case of the
+Bor\o{u}vka's algorithm, whose proof of correctness in Lemma \ref{borcorr} explicitly referred to
+distinct weights and indeed, if they are not distinct, the algorithm will occasionally produce
+cycles. To avoid the cycles, the ties in edge weight comparisons have to be broken in a~systematic
+way. The same applies to the contractive version of this algorithm.
+
 \endpart