From b3eecfc2246bbb4e455825a59df914f2b2e0eb09 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Jan 2008 14:50:58 +0100 Subject: [PATCH] The beginning of MST chapter. --- biblio.bib | 30 ++++++++++++++++++ macros.tex | 11 +++++-- mst.tex | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 129 insertions(+), 4 deletions(-) diff --git a/biblio.bib b/biblio.bib index e1ed226..705c7ae 100644 --- a/biblio.bib +++ b/biblio.bib @@ -121,6 +121,26 @@ note = "Czech with German summary" } +@article { boruvka:networks, + author = "Otakar Bor{\accent23u}vka", + title = "{P\v{r}\'\i{}sp\v{e}vek k~\v{r}e\v{s}en\'\i{} ot\'azky ekonomick\'e stavby elektrovodn\'\i{}ch s\'\i{}t\'\i{} (Contribution to the solution of a problem of economical construction of electric networks)}", + journal = "Elektronick\'y obzor", + volume = "15", + year = "1926", + pages = "153--154", + note = "Czech" +} + +@article { jarnik:ojistem, + author = "Vojtech Jarn\'\i{}k", + title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}", + journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}", + volume = "VI", + year = "1930", + pages = "57--63", + note = "Czech" +} + @book { tarjan:dsna, author = "Robert E. Tarjan", title = "{Data structures and network algorithms}", @@ -264,3 +284,13 @@ year={2003}, publisher={ACM Press New York, NY, USA} } + +@article{ graham:msthistory, + title={{On the history of the minimum spanning tree problem}}, + author={Graham, R.L. and Hell, P.}, + journal={Annals of the History of Computing}, + volume={7}, + number={1}, + pages={43--57}, + year={1985} +} diff --git a/macros.tex b/macros.tex index b244eb1..5834507 100644 --- a/macros.tex +++ b/macros.tex @@ -27,15 +27,17 @@ %%% Miscellanea %%% \def\em#1{{\it #1\/}} +\def\df#1{{\it #1\/}} % when we define something \def\O{{\cal O}} \def\<#1>{\leavevmode\hbox{\it #1\/}} \let\>=\noindent \def\qed{{\parfillskip=0pt\allowbreak\hfill\nobreak $\spadesuit$\par}} +\def\FIXME#1{\>{\bo FIXME:} #1} % Footnotes \newcount\footcnt \footcnt=0 -\def\foot#1{\global\advance\footcnt by 1{\parindent=0.25in\parskip=0pt\footnote{$^{\left<\the\footcnt\right>}$}{#1}}} +\def\foot#1{\global\advance\footcnt by 1{\parindent=0.25in\parskip=0pt\footnote{$^{\the\footcnt}$}{#1}}} %%% Fonts %%% @@ -285,12 +287,15 @@ } \def\proclaim#1{\advance\thmcount by 1 -\noindent {\bf #1 \the\chapcount.\the\seccount.\the\thmcount. } -} +\noindent {\bo #1 \the\chapcount.\the\seccount.\the\thmcount.\enspace}} \def\theorem{\proclaim{Theorem}} \def\lemma{\proclaim{Lemma}} \def\defn{\proclaim{Definition}} +\def\problem{\proclaim{Problem}} +\def\obs{\proclaim{Observation}} + +\def\lemman#1{\proclaim{Lemma}{\sl (#1)\/}} \def\proof{\noindent {\sl Proof.} } diff --git a/mst.tex b/mst.tex index 33852d1..ee53099 100644 --- a/mst.tex +++ b/mst.tex @@ -6,8 +6,98 @@ \section{The Problem} -\cite{boruvka:ojistem} +The problem of finding a minimum spanning tree of a weighted graph is one of the +best studied problems in the area of combinatorial optimization and it can be said +that it stood at the cradle of this discipline. Its colorful history (see \cite{graham:msthistory} +and \cite{nesetril:history} for the full account) begins in~1926 with +the pioneering work of Bor\accent23uvka +\cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.}, +who studied primarily an Euclidean version of the problem related to planning +of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient +algorithm for the general version of the problem. As it was well before the birth of graph +theory, the language of his paper was complicated, so we will rather state the problem +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}$: +\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. +\endlist + +Bor\accent23uvka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in +mostly geometric setting, giving another polynomial algorithm. However, when +computer science and graph theory started forming in the 1950's and the +spanning tree problem was one of the central topics of the flourishing new +disciplines, the previous work was not well known and the algorithms have been +rediscovered several times. + +Recently, several significantly faster algorithms were discovered, most notably the +$\O(m\beta(m,n))$-time algorithm by Fredman and Tarjan \cite{ft:fibonacci} and +algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann} +and Pettie \cite{pettie:ackermann}. + +\FIXME{Write the rest of the history.} + +This chapter attempts to survery the important algorithms for finding the MST and it +also presents several new ones. + +\section{Basic Properties} + +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}. + +First of all, let us show that the weights on edges are not necessary for the +definition of the MST. We can formulate an equivalent characterization using +an ordering of edges instead. + +\defn For a graph~$G$ and its tree subgraph~$T$, we define: +\itemize\ibull +\:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$. +\:For an edge $e=xy$ outside~$T$, we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and + the edges of this path \df{edges covered by~$e$}. +\:An edge~$e=xy$ outside~$T$ is called \df{$T$-light} if it covers a heavier edge, i.e., if there + is an edge $f\in T[e]$ such that $w(f) > w(e)$. +\:An edge~$e$ outside~$T$ is called \df{$T$-heavy} if it is not light. +\endlist + +\theorem A~spanning tree~$T$ of a graph~$G$ is minimal iff there is no $T$-light edge in~$G$. + +To prove this theorem, we will use a notion of edge exchanges, similar to Steinitz theorem +in linear algebra or the exchanges in matroid theory. +\FIXME{reference} + +\defn For a tree~$T$ and edges $e\in T$ and $f\not\in T$, the \df{exchange} +XXXXXX + +For the other implication, we will make use of the following lemmata, again +based on exchange of edges: + +{\narrower +\lemman{Exchange property of spanning trees} +Let $T$ and $T'$ be spanning trees of a common graph~$G$. Then there exists +a sequence + +} + +Back to the proof of the theorem: + +The implication $\Rightarrow$ is straightforward: If there is a $T$-light edge~$e$, there +exists an edge $f\in T[e]$ such that $w(f)>w(e)$. Now $T-f$ is a forest of two trees +with endpoints of~$e$ located in different components, so adding $e$ to this forest +must restore connectivity and $T'=T-f+e$ is another spanning tree with weight $w(T') = w(T)-w(f)+w(e) < w(T)$. +Hence $T$ could not have been minimal. + + +%\:For a disconnected graph~$G$, we define the \df{(minimal) spanning forest (or MSF)} +% as an union of (minimal) spanning trees of its connected components. % mention Steiner trees +% mention matroids +% sorted weights \endpart -- 2.39.2