Final typesetting: Chapters 1 and 2.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index e36ce9d09439c720cab61ed1d86267ad54325713..9729a06167e56c6e3402589f30df6cff9d23bf26 100644 (file)
--- a/mst.tex
+++ b/mst.tex
@@ -147,7 +147,7 @@ Let us consider an edge $f\in T'\setminus T^*$. We want to show that $f$ is not
 $T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is
 either identical to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$,
 where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter we have
-$w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter
+$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
 
@@ -183,6 +183,7 @@ edge exchanges going from $T_1$ to $T_2$. As all edge weights all distinct,
 these edge exchanges must be in fact strictly increasing. On the other hand,
 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.
+\looseness=1  %%HACK%%
 \qed
 
 \nota\id{mstnota}%
@@ -404,13 +405,13 @@ application of the Blue rule. We stop when the blue subgraph is connected, so
 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
+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_1,v_1]\,v_1u_2\,T_2[u_2,v_2]\,v_2u_3\,T_3[u_3,v_3]\, \ldots \,T_k[u_k,v_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,
-getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a contradiction.
+getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a~contradiction.
 (Note that distinctness of edge weights was crucial here.)
 \qed
 
@@ -686,7 +687,7 @@ 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~$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.$$
+their counterparts in~$G/e$. Then $\mst(G) = \pi^{-1}[\mst(G/e)] + e.$
 
 \proof
 % We seem not to need this lemma for multigraphs...
@@ -740,7 +741,7 @@ have arbitrary weights that are heavier than the edges of all the distractors.
 \figure{hedgehog.eps}{\epsfxsize}{A~hedgehog $H_{5,2}$ (quills bent to fit in the picture)}
 
 \lemma
-A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a graph isomorphic with $H_{a,k-1}$.
+A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a~graph isomorphic with $H_{a,k-1}$.
 
 \proof
 Each vertex is incident with an edge of some distractor, so the algorithm does not select