From d653340595b7286054572744030d87372b1b34f0 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Jan 2008 19:43:37 +0100 Subject: [PATCH] Red-Blue section started. --- Makefile | 2 +- biblio.bib | 9 ++++++ macros.tex | 10 +++--- mst.tex | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++-- notation.tex | 2 ++ 5 files changed, 102 insertions(+), 8 deletions(-) diff --git a/Makefile b/Makefile index 1a19b1e..9802547 100644 --- a/Makefile +++ b/Makefile @@ -2,7 +2,7 @@ all: saga.ps CHAPTERS=cover mst notation -%.dvi: %.tex macros.tex +%.dvi: %.tex macros.tex biblio.bib tex $< && if grep -q citation $*.aux ; then bibtex $* && tex $< && tex $< ; fi saga.dvi: $(addsuffix .tex,$(CHAPTERS)) diff --git a/biblio.bib b/biblio.bib index 705c7ae..45d4595 100644 --- a/biblio.bib +++ b/biblio.bib @@ -294,3 +294,12 @@ pages={43--57}, year={1985} } + +@article{ cayley:trees, + title={{A theorem on trees}}, + author={Cayley, Arthur}, + journal={Quart. J. Math}, + volume={23}, + year={1889}, + pages={376--378} +} diff --git a/macros.tex b/macros.tex index 149b875..270d095 100644 --- a/macros.tex +++ b/macros.tex @@ -232,14 +232,13 @@ % \algout popis vystupu % \endalgo -\def\algo#1{ +\def\algo{ \interlistskip \begingroup \let\:=\algoitem \parskip=1pt plus 1pt minus 0.3pt \rightskip=2em \itemcount=0 -{\bo Algoritmus\/} {\sc #1} } \def\endalgo{\interlistskip\endgroup} \def\algopar{\par @@ -255,8 +254,8 @@ \futurelet\next\algoitemh} \def\algoitemh{\ifx\next:\let\next=\algohang\else\let\next=\relax\fi\next} \def\algohang:{\advance\hangindent by 2em \hskip 2em\futurelet\next\algoitemh} -\def\algin{\par{\it Vstup:\/} } -\def\algout{\par{\it Výstup:\/} } +\def\algin{\par{\sl Input:\/} } +\def\algout{\par{\sl Output:\/} } %%% Constructs used in algorithms %%% @@ -296,11 +295,14 @@ \def\problem{\proclaim{Problem}} \def\obs{\proclaim{Observation}} \def\rem{\proclaim{Remark}} +\def\alg{\proclaim{Algorithm}} \def\label#1{{\sl (#1)\/}\enspace} +\def\theoremn{\theorem\label} \def\lemman{\lemma\label} \def\defnn{\defn\label} +\def\algn{\alg\label} \def\proof{\noindent {\sl Proof.}\enspace} diff --git a/mst.tex b/mst.tex index baa178e..ff08ec8 100644 --- a/mst.tex +++ b/mst.tex @@ -21,11 +21,15 @@ in contemporary terminology: \proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$, find its minimum spanning tree, where: -\defn For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$: +\defn\thmid{mstdef}% +For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$: \itemize\ibull \:A~tree $T$ is a \df{spanning tree} of~$G$ if and only if $V(T)=V(G)$ and $E(T)\subseteq E(G)$. \:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$. \:A~spanning tree~$T$ is \df{minimal} iff $w(T)$ is the smallest possible of all spanning trees. + We use an abbreviation \df{MST} for such trees. +\:For a disconnected graph, a \df{(minimal) spanning forest (MSF)} is defined as + a union of (minimal) spanning trees of its connected components. \endlist Bor\accent23uvka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in @@ -74,7 +78,7 @@ Let~$T$ be a~spanning tree. Then: Please note that the above properties also apply to tree edges which by definition cover only themselves and therefore they are always heavy. -\lemma\thmid{lightlemma}% +\lemman{Light edges}\thmid{lightlemma}% Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$ is not minimal. @@ -145,11 +149,88 @@ If~$T$ is minimal, then by Lemma~\thmref{lightlemma} there are no $T$-light edges. Conversely, when $T$ is a spanning tree without $T$-light edges and $T_{min}$ is an arbitrary minimal spanning tree, then according to the Monotone -exchange lemma~\thmref{monoxchg} there exists a non-decreasing sequence +exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$ and thus $T$~is also minimal. \qed +In general, a single graph can have many minimal spanning trees (for example +a complete graph on~$n$ vertices and unit edge weights has $n^{n-2}$ +minimum spanning trees according to the Cayley's formula \cite{cayley:trees}). +However, this is possible only if the weight function is not injective. + +\lemman{MST uniqueness} +If all edge weights are distinct, then the minimum spanning tree is unique. + +\proof +Consider two minimal spanning trees $T_1$ and~$T_2$. According to the previous +theorem, there are no light edges with respect to neither of them, so by the +Monotone exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence +of edge exchanges going from $T_1$ to $T_2$. Each exchange in this sequence is +strictly increasing, because all edge weights all distinct. 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. +\qed + +\rem\thmid{edgeoracle}% +To simplify the description of MST algorithms, we will expect that the input +graph has all edge weights distinct. We will also assume that instead of explicit +edge weights we will be given a comparison oracle, that is a function which answers +questions ``$w(e)