From a41bbc241e18a0dbf262ada06df9199aced0b682 Mon Sep 17 00:00:00 2001
From: Martin Mares <mj@ucw.cz>
Date: Sat, 19 Apr 2008 22:52:55 +0200
Subject: [PATCH] Cleaned up the Red-Blue section.

---
 dyn.tex |  2 +-
 mst.tex | 89 ++++++++++++++++++++++++++++++---------------------------
 opt.tex |  4 +--
 3 files changed, 50 insertions(+), 45 deletions(-)

diff --git a/dyn.tex b/dyn.tex
index a2bb4cc..31beea1 100644
--- a/dyn.tex
+++ b/dyn.tex
@@ -555,7 +555,7 @@ edges for~$e$, the lightest one is at the maximum level.
 
 \proof
 Let us consider any two edges $f_1$ and~$f_2$ replacing~$e$. By minimality of~$F$ and the Cycle
-rule (\ref{cyclerule}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$.
+rule (Lemma \ref{redlemma}), each $f_i$ is the heaviest edge on the cycle~$C_i = F[f_i] + f_i$.
 In a~moment, we will show that the symmetric difference~$C$ of these two cycles is again a~cycle.
 This implies that if $f_1$ is heavier than~$f_2$, then $f_1$~is the heaviest edge on~$C$, so
 $\ell(f_1) \le \ell(f_2)$ by I3. Therefore the lightest of all replacement edges must have
diff --git a/mst.tex b/mst.tex
index 445b6ce..449d890 100644
--- a/mst.tex
+++ b/mst.tex
@@ -48,7 +48,7 @@ and Pettie \cite{pettie:ackermann}, to another algorithm by Pettie \cite{pettie:
 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.
@@ -185,17 +185,23 @@ $T_1$ and $T_2$ must be identical.
 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.
+\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:
 
@@ -222,7 +228,7 @@ the edge $\pi[e]\in E(G_2)$ is~$f[T]$-light). Therefore by the Minimality Theore
 \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
@@ -234,7 +240,7 @@ Most MST algorithms can be described as special cases of the following procedure
 \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
@@ -245,27 +251,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}\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}
@@ -279,10 +297,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}
@@ -303,19 +321,6 @@ 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
 
-\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
@@ -340,7 +345,7 @@ 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
-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
diff --git a/opt.tex b/opt.tex
index 632fd4e..bb07164 100644
--- a/opt.tex
+++ b/opt.tex
@@ -588,7 +588,7 @@ Let us show that edges of~$G$ that do not belong to the right-hand side
 do not belong to the left-hand side either.
 We know that the edges that
 do not participate in the MSF of some graph are exactly those which are the heaviest
-on some cycle (this is the Cycle rule, \ref{cyclerule}).
+on some cycle (this is the Cycle rule from Lemma \ref{redlemma}).
 
 Whenever an~edge~$g$ lies in~$C$, but not in~$\msf(C)$, then $g$~is the heaviest edge
 on some cycle in~$C$. As this cycle is also contained in~$G$, the edge $g$~does not participate
@@ -906,7 +906,7 @@ $H=\bigcup_i C_i$.
 The first and second condition of the definition of compartments follow
 from the Partitioning theorem (\ref{partthm}), so it remains to show that $\msf(H)$
 is the union of the MSF's of the individual compartments. By the Cycle rule
-(\ref{cyclerule}), an~edge $h\in H$ is not contained in $\msf(H)$ if and only if
+(Lemma \ref{redlemma}), an~edge $h\in H$ is not contained in $\msf(H)$ if and only if
 it is the heaviest edge on some cycle. It is therefore sufficient to prove that
 every cycle in~$H$ is contained within a~single~$C_i$.
 
-- 
2.39.2