Corrections of errors mentioned by Patrice.

[saga.git] / mst.tex

diff --git a/mst.tex b/mst.tex
index 3f715954dd69cdaeb575751369442f8f562971f9..820ba51afd3bd4be0aa95a636f6059983ba1095d 100644 (file)
--- 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 that 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.
@@ -50,15 +50,16 @@ 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,
 various approaches to the problem including randomization and solving of important
-special cases.
+special cases. At several places, we will try to contribute our little stones to this
+mosaic.
 
 %--------------------------------------------------------------------------------
 
 \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~connected graph~$G$ with edge weights~$w$ and all
 other graphs will be spanning subgraphs of~$G$. We will use the same notation
@@ -80,9 +81,9 @@ Let~$T$ be a~spanning tree. Then:
 \endlist
 
 \rem
-Edges of the tree~$T$ itself are neither heavy nor light. We will sometimes
-use the name \df{non-heavy} for edges which are either light or contained
-in the tree.
+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$
@@ -126,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.
@@ -421,7 +422,7 @@ by the lightest neighboring edge until it spans the whole graph.
 \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