Cover of the abstract.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index 9aa9bdf0881f59519c5af3922855453b903a853b..5cccbb9810448adefd7980aa99b52adcebc11ac5 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
 
@@ -480,7 +481,7 @@ From this, we can conclude:
 The 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}.
+We will show several faster implementations in Section \ref{iteralg}.
 
 \paran{Kruskal's algorithm}%
 The last of the three classical algorithms processes the edges of the
@@ -655,7 +656,7 @@ in all iterations is $\O(\sum_i n_i^2) = \O(\sum_i n^2/4^i) = \O(n^2)$.
 
 On planar graphs, the algorithm runs much faster:
 
-\thmn{Contractive Bor\o{u}vka on planar graphs, \cite{mm:mst}}\id{planarbor}%
+\thmn{Contractive Bor\o{u}vka on planar graphs}\id{planarbor}%
 When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
 time $\O(n)$.
 
@@ -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