From 6fc3a3466d9f8fe4f5bce1e1e3a2179c4c4fc8ea Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 17 Jan 2008 21:25:53 +0100 Subject: [PATCH] Finished the RB alg. --- mst.tex | 173 +++++++++++++++++++++++++++++++-------------------- notation.tex | 9 ++- 2 files changed, 110 insertions(+), 72 deletions(-) diff --git a/mst.tex b/mst.tex index b75f344..62d571b 100644 --- a/mst.tex +++ b/mst.tex @@ -7,36 +7,36 @@ \section{The Problem} 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 +best studied problems in the area of combinatorial optimization since its birth. +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 +algorithm for the general version of the problem. As it was well before the dawn of graph +theory, the language of his paper was complicated, so we will better 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: +find its minimum spanning tree, defined as follows: \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)$. +\: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 which is a tree. \: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. +\:A~\df{minimum spanning tree (MST)} of~$G$ is a spanning tree~$T$ such that its weight $w(T)$ + is the smallest possible of all the spanning trees of~$G$. +\:For a disconnected graph, a \df{(minimum) spanning forest (MSF)} is defined as + a union of (minimum) spanning trees of its connected components. \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 +mostly geometric setting, giving another efficient 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 +disciplines, the previous work was not well known and the algorithms had to be rediscovered several times. Recently, several significantly faster algorithms were discovered, most notably the @@ -55,9 +55,9 @@ In this section, we will examine the basic properties of spanning trees and prov several important theorems to base the algorithms upon. We will follow the theory developed by Tarjan in~\cite{tarjan:dsna}. -For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all other -graphs will be subgraphs of~$G$ containing all of its vertices. We will use the -same notation for the subgraph and for the corresponding set of edges. +For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all +other graphs will be spanning subgraphs of~$G$. We will use the same notation +for the subgraphs as for the corresponding sets of edges. 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 @@ -69,7 +69,7 @@ Let~$T$ be a~spanning tree. Then: \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$. \:For an edge $e=xy$ 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$ is called \df{$T$-light} if it covers a heavier edge, i.e., if there +\:An edge~$e$ is called \df{light with respect to~$T$} (or just \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$ is called \df{$T$-heavy} if it is not $T$-light. \endlist @@ -80,14 +80,14 @@ which by definition cover only themselves and therefore they are always heavy. \lemman{Light edges}\thmid{lightlemma}% Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$ -is not minimal. +is not minimum. \proof -If there is a $T$-light edge~$e$, then 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$ +If there is a $T$-light edge~$e$, then there exists an edge $e'\in T[e]$ such +that $w(e')>w(e)$. Now $T-e'$ 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. +connectivity and $T':=T-e'+e$ is another spanning tree with weight $w(T') += w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum. \qed \figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\thmref{lightlemma}} @@ -106,9 +106,9 @@ there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that $T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$. \proof -By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$, then -both trees are identical and an empty sequence suffices. Otherwise, the trees are different, -but they are of the same size, so there must exist an edge $e'\in T'\setminus T$. +By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$, +both trees are identical and no exchanges are needed. Otherwise, the trees are different, +but as they are of the same size, there must exist an edge $e'\in T'\setminus T$. The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction @@ -118,7 +118,7 @@ hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence. \figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}} \lemman{Monotone exchanges}\thmid{monoxchg}% -Let $T$ be a spanning tree such that there are no $T$-light edges and $T$ +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. @@ -126,62 +126,64 @@ transforming $T$ to~$T'$ such that the weight does not increase in any step. We improve the argument from the previous proof, refining the induction step. When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$, the weight never drops, since $e'$ is not a $T$-light edge and therefore -$w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\le w(T)$. - -To allow the induction to proceed, we have to make sure that there are still -no light edges with respect to~$T^*$. In fact, it is enough to avoid $T^*$-light -edges in $T'\setminus T^*$, since these are the only edges considered by the -induction step. Instead of picking $e'$ arbitrarily, we will pick the lightest -edge available. Now consider an edge $f\in T'\setminus T^*$. We want to show -that $f$ is heavier than all edges on $T^*[f]$. - -The path $T^*[f]$ is either the original path $T[f]$ (if $e\not\in T[f]$) -or $T[f] \symdiff C$, where $C$ is the cycle $T[e']+e$. The first case is -trivial, in the second case $w(f)\ge w(e')$ and all other edges on~$C$ -are lighter than~$e'$. +$w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\ge w(T)$. + +To keep the induction going, we have to make sure that there are still no light +edges with respect to~$T^*$. In fact, it is enough to avoid such edges in +$T'\setminus T^*$, since these are the only edges considered by the induction +steps. To accomplish that, we replace the so far arbitrary choice of $e'\in T'\setminus T$ +by picking the lightest such edge. + +Now 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 equal 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 one +$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 -\theorem -A~spanning tree~$T$ is minimal iff there is no $T$-light edge. +\theorem\thmid{mstthm}% +A~spanning tree~$T$ is minimum iff there is no $T$-light edge. \proof -If~$T$ is minimal, then by Lemma~\thmref{lightlemma} there are no $T$-light +If~$T$ is minimum, 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 +and $T_{min}$ is an arbitrary minimum spanning tree, then according to the Monotone 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. +and thus $T$~is also minimum. \qed -In general, a single graph can have many minimal spanning trees (for example +In general, a single graph can have many minimum 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, as the following lemma shows, this is possible only if the weight +However, as the following theorem shows, this is possible only if the weight function is not injective. -\lemman{MST uniqueness} +\theoremn{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 +Consider two minimum 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, +Monotone exchange lemma (\thmref{monoxchg}) there exists a sequence of non-decreasing +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. \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)\hbox to 6em{#1 \dotfill} #2} \def\[#1]{[\thmref{#1}]} \n{$T[x,y]$}{the path in a tree~$T$ joining $x$ and $y$ \[heavy]} -\n{$T[e]$}{the path in a tree~$T$ joining endpoints of an~edge~$e$ \[heavy]} +\n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]} \n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$} \n{$G-e$}{graph $G$ with edge $e$ removed} \n{$G+e$}{graph $G$ with edge $e$ added} \n{$w(e)$}{weight of an edge $e$} -\n{$V(G)$}{the set of vertices of a graph~$G$} -\n{$E(G)$}{the set of edges of a graph~$G$} +\n{$V(G)$}{set of vertices of a graph~$G$} +\n{$E(G)$}{set of edges of a graph~$G$} +\n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$} +\n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$} +\n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm} \n{MST}{minimal spanning tree \[mstdef]} \n{MSF}{minimal spanning forest \[mstdef]} } -- 2.39.5