whose time complexity is provably optimal.
In the upcoming chapters, we will explore this colorful universe of MST algorithms.
-We will meet the standard works of the classics, the clever ideas of their successors,
+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.
When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote
its unique minimum spanning tree.
-\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.
+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 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 distinct edge weights and $\pi$
-their monotone isomorphism. Then $\mst(G_2) = \pi[\mst(G_1)]$.
+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
\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
\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
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}\id{bluelemma}%
-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$.
+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
+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}\id{redlemma}%
-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}
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}
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
lemma all other (red) edges are outside~$T_{min}$, so the blue edges are exactly~$T_{min}$.
\qed
-\para
-The Red lemma actually works in both directions and it can be used to characterize
-all non-MST edges, which will turn out to be useful in the latter chapters.
-
-\corn{Cycle rule}\id{cyclerule}%
-An~edge~$e$ is not contained in the MST iff it is the heaviest on some cycle.
-
-\proof
-The implication from the right to the left is the Red lemma. In the other
-direction, when~$e$ is not contained in~$T_{min}$, it is $T_{min}$-heavy (by
-Theorem \ref{mstthm}), so it is the heaviest edge on the cycle $T_{min}[e]+e$.
-\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
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
-pAroceed with the next iteration.
+proceed with the next iteration.
\algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst} and others}
\algo
\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
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,
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.
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{iteralg}.
\qed
\impl
-Except for the initial sorting, which in general takes $\Theta(m\log m)$ time, the only
+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 closely related to the well-known Disjoint Set Union problem:
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.
\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
\:While $n(G)>1$:
\::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 $G$ along 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$.}
+\::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
\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_k$, 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_i)$ time.
\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
In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$.
\paran{A~lower bound}%
-Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity
+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$
edges as every $H_{a,k}$ contains a complete graph on~$a$ vertices.
\qed
-\remn{Disconnected graphs}\id{disconn}%
+%--------------------------------------------------------------------------------
+
+\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
$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