From 14608799be06fdd7e85a9e5517ed5f4df3e63b79 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 20 Jan 2008 20:48:56 +0100 Subject: [PATCH] Simplify the reference macros. --- macros.tex | 18 ++++++++---------- mst.tex | 54 ++++++++++++++++++++++++++-------------------------- notation.tex | 6 +++--- 3 files changed, 38 insertions(+), 40 deletions(-) diff --git a/macros.tex b/macros.tex index ca99e44..42b162d 100644 --- a/macros.tex +++ b/macros.tex @@ -273,24 +273,28 @@ \chapcount=0 \seccount=0 \thmcount=0 +\def\currentid{??} \def\chapter#1{\vfill\supereject \advance\chapcount by 1 \seccount=0 \thmcount=0 -\leftline{\chapfont\the\chapcount. #1} +\edef\currentid{\the\chapcount} +\leftline{\chapfont\currentid. #1} \bigskip } \def\section#1{\bigskip \advance\seccount by 1 \thmcount=0 -\leftline{\secfont\the\chapcount.\the\seccount. #1} +\edef\currentid{\the\chapcount.\the\seccount} +\leftline{\secfont\currentid. #1} \medskip } \def\proclaim#1{\advance\thmcount by 1 -\noindent {\bo \the\chapcount.\the\seccount.\the\thmcount.\enspace #1.\enspace}} +\edef\currentid{\the\chapcount.\the\seccount.\the\thmcount} +\noindent {\bo \currentid.\enspace #1.\enspace}} \def\thm{\proclaim{Theorem}} \def\lemma{\proclaim{Lemma}} @@ -334,13 +338,7 @@ \fi } -\def\chapid#1{\writeid{ch#1}{\the\chapcount}} -\def\secid#1{\writeid{sec#1}{\the\chapcount.\the\seccount}} -\def\thmid#1{\writeid{thm#1}{\the\chapcount.\the\seccount.\the\thmcount}} - -\def\chapref#1{\ref{ch#1}} -\def\secref#1{\ref{sec#1}} -\def\thmref#1{\ref{thm#1}} +\def\id#1{\writeid{#1}{\currentid}} %%% Bibliography %%% diff --git a/mst.tex b/mst.tex index 8eb0baf..2925414 100644 --- a/mst.tex +++ b/mst.tex @@ -20,7 +20,7 @@ in contemporary terminology: \proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$, find its minimum spanning tree, defined as follows: -\defn\thmid{mstdef}% +\defn\id{mstdef}% 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)$. @@ -65,7 +65,7 @@ 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. -\defnn{Heavy and light edges}\thmid{heavy}% +\defnn{Heavy and light edges}\id{heavy}% Let~$T$ be a~spanning tree. Then: \itemize\ibull \:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$. @@ -80,7 +80,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. -\lemman{Light edges}\thmid{lightlemma}% +\lemman{Light edges}\id{lightlemma}% Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$ is not minimum. @@ -92,7 +92,7 @@ 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}} +\figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\ref{lightlemma}} The converse of this lemma is also true and to prove it, we will once again use technique of transforming trees by \df{exchanges} of edges. In the proof of the @@ -101,7 +101,7 @@ a spanning tree for another edge~$f$ covered by~$e$, the result is again a spanning tree. In fact, it is possible to transform any spanning tree to any other spanning tree by a sequence of exchanges. -\lemman{Exchange property for trees}\thmid{xchglemma}% +\lemman{Exchange property for trees}\id{xchglemma}% Let $T$ and $T'$ be spanning trees of a common graph. Then there exists a sequence of edge exchanges which transforms $T$ to~$T'$. More formally, there exists a sequence of spanning trees $T=T_0,T_1,\ldots,T_k=T'$ such that @@ -117,9 +117,9 @@ tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the inductio hypothesis to $T^*$ and $T'$ to get the rest of the exchange sequence. \qed -\figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}} +\figure{mst1.eps}{295pt}{One step of the proof of Lemma~\ref{xchglemma}} -\lemman{Monotone exchanges}\thmid{monoxchg}% +\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. @@ -144,15 +144,15 @@ $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 -\thm\thmid{mstthm}% +\thm\id{mstthm}% A~spanning tree~$T$ is minimum iff there is no $T$-light edge. \proof -If~$T$ is minimum, then by Lemma~\thmref{lightlemma} there are no $T$-light +If~$T$ is minimum, then by Lemma~\ref{lightlemma} there are no $T$-light edges. Conversely, when $T$ is a spanning tree without $T$-light edges and $T_{min}$ is an arbitrary minimum spanning tree, then according to the Monotone -exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence +exchange lemma (\ref{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 minimum. \qed @@ -169,14 +169,14 @@ If all edge weights are distinct, then the minimum spanning tree is unique. \proof 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 sequence of non-decreasing +Monotone exchange lemma (\ref{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}% +\rem\id{edgeoracle}% To simplify the description of MST algorithms, we will expect that the weights of all edges are distinct and that instead of numeric weights (usually accompanied by problems with representation of real numbers in algorithms) we will be given @@ -187,7 +187,7 @@ minimum spanning trees, the unique MST of the new graph will still be a MST of t original graph. In the few cases where we need a more concrete input, we will explicitly state so. -\nota\thmid{mstnota}% +\nota\id{mstnota}% When $G$ is a graph with distinct edge weights, we will use $\mst(G)$ to denote its unique minimum spanning tree. @@ -198,7 +198,7 @@ Most MST algorithms can be described as special cases of the following procedure \algn{Red-Blue Meta-Algorithm} \algo -\algin A~graph $G$ with an edge comparison oracle (see \thmref{edgeoracle}) +\algin A~graph $G$ with an edge comparison oracle (see \ref{edgeoracle}) \:In the beginning, all edges are colored black. \:Apply rules as long as possible: \::Either pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue, \cmt{Blue rule} @@ -250,7 +250,7 @@ Assume that $e=xy$ be a black edge. Let us denote $M$ the set of vertices reachable from~$x$ using only blue edges. If $y$~lies in~$M$, then $e$ together with some blue path between $x$ and $y$ forms a cycle and it must be the heaviest edge on this cycle. This holds because all blue edges have been already proven -to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\thmref{mstthm}). +to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\ref{mstthm}). In this case we can apply the red rule. On the other hand, if $y\not\in M$, then the cut formed by all edges between $M$ @@ -311,7 +311,7 @@ of the cycle). Then $e_2=v_2u_3$ and $w(e_2)w which is a contradiction. (Note that distinctness of edge weights was crucial here.) \qed -\lemma\thmid{boruvkadrop}% +\lemma\id{boruvkadrop}% In each iteration of the algorithm, the number of trees in~$T$ drops at least twice. \proof @@ -322,7 +322,7 @@ consists of at least two original trees. \cor The algorithm stops in $\O(\log n)$ iterations. -\lemma\thmid{boruvkaiter}% +\lemma\id{boruvkaiter}% Each iteration can be carried out in time $\O(m)$. \proof @@ -383,7 +383,7 @@ From this, we can conclude: Jarn\'\i{}k's algorithm finds the MST of the graph in time $\O(m\log n)$. \rem -We will show several faster implementations in section \secref{fibonacci}. +We will show several faster implementations in section \ref{fibonacci}. \algn{Kruskal \cite{kruskal:mst}, the Greedy algorithm} \algo @@ -456,13 +456,13 @@ There are two definitions of edge contraction which differ when an edge of a triangle is contracted. Either we unify the other two edges to a single edge or we keep them as two parallel edges, leaving us with a~multigraph. We will use the multigraph version and show that we can easily reduce the multigraph -to a simple graph later. (See \thmref{contract} for the exact definitions.) +to a simple graph later. (See \ref{contract} for the exact definitions.) We only need to be able to map edges of the contracted graph to the original edges, so each edge will carry a unique label $\ell(e)$ which will be preserved by contractions. -\lemman{Flattening a multigraph}\thmid{flattening}% +\lemman{Flattening a multigraph}\id{flattening}% Let $G$ be a multigraph and $G'$ its subgraph such that all loops have been removed and each bundle of parallel edges replaced by its lightest edge. Then $G'$~has the same MST as~$G$. @@ -498,7 +498,7 @@ Each iteration of the algorithm can be carried out in time~$\O(m)$. \proof The only non-trivial parts are steps 6 and~7. Contractions can be handled similarly -to the unions in the original Bor\o{u}vka's algorithm (see \thmref{boruvkaiter}). +to the unions in the original Bor\o{u}vka's algorithm (see \ref{boruvkaiter}). We build an auxillary graph containing only the selected edges~$e_i$, find connected components of this graph and renumber vertices in each component to the identifier of the component. This takes $\O(m)$ time. @@ -529,7 +529,7 @@ the $i$-th iteration takes $\O(m_i)$ time. We are going to prove that the $m_i$'s are decreasing exponentially. The number of trees in the non-contracting version of the algorithm decreases -at least twice in each iteration (Lemma \thmref{boruvkadrop}) and the +at least twice in each iteration (Lemma \ref{boruvkadrop}) and the same must hold for the number of vertices in the contracting version. Therefore $n_i\le n/2^i$. @@ -573,12 +573,12 @@ their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$ \proof % We seem not to need this lemma for multigraphs... %If there are any loops or parallel edges in~$G$, we can flatten the graph. According to the -%Flattening lemma (\thmref{flattening}), the MST stays the same and if we remove a parallel edge +%Flattening lemma (\ref{flattening}), the MST stays the same and if we remove a parallel edge %or loop~$f$, then $\pi(f)$ would be removed when flattening~$G/e$, so $f$ never participates %in a MST. The right-hand side of the equality is a spanning tree of~$G$, let us denote it by~$T$ and the MST of $G/e$ by~$T'$. If $T$ were not minimum, there would exist a $T$-light edge~$f$ in~$G$ -(according to Theorem \thmref{mstthm}). If the path $T[f]$ covered by~$f$ does not contain~$e$, +(according to Theorem \ref{mstthm}). If the path $T[f]$ covered by~$f$ does not contain~$e$, then $\pi[T[f]]$ is a path covered by~$\pi(f)$ in~$T'$. Otherwise $\pi(T[f]-e)$ is such a path. In both cases, $f$ is $T'$-light, which contradicts the minimality of~$T'$. (We do not have a~multigraph version of the theorem, but this direction is a straightforward edge exchange, @@ -654,7 +654,7 @@ closed on contractions and have bounded density. \defn A~graph~$H$ is a \df{minor} of a~graph~$G$ iff it can be obtained -from a subgraph of~$G$ by a sequence of graph contractions (see \thmref{simpcont}). +from a subgraph of~$G$ by a sequence of graph contractions (see \ref{simpcont}). \defn A~class~$\cal C$ of graphs is \df{minor-closed}, when for every $G\in\cal C$ and @@ -666,7 +666,7 @@ Non-trivial minor-closed classes include planar graphs and more generally graphs embeddable in any fixed surface. Many nice properties of planar graphs extend to these classes, too, most notable the linearity of the number of edges. -\defn\thmid{density}% +\defn\id{density}% Let $\cal C$ be a class of graphs. We define its \df{edge density} $\varrho(\cal C)$ to be the infimum of all~$\varrho$'s such that $\vert E(G) \vert \le \varrho\cdot\vert V(G)\vert$ holds for every $G\in\cal C$. @@ -682,7 +682,7 @@ See Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalen \section{Using Fibonacci heaps} -\secid{fibonacci} +\id{fibonacci} % G has to be connected, so m=O(n) % mention Steiner trees diff --git a/notation.tex b/notation.tex index 59552c9..4b3bd1f 100644 --- a/notation.tex +++ b/notation.tex @@ -6,7 +6,7 @@ {\obeylines\parskip=0pt \def\n#1#2{\>\hbox to 6em{#1 \dotfill} #2} -\def\[#1]{[\thmref{#1}]} +\def\[#1]{[\ref{#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 the endpoints of an~edge~$e$ \[heavy]} \n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$} @@ -47,7 +47,7 @@ shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we consider multigraphs with no multiple edges nor loops and simple graphs to be the same objects, although they formally differ. -\defn\thmid{contract}% +\defn\id{contract}% Let $G=(V,E,M)$ be a multigraph and $e=xy$ its edge. \df{(Multigraph) contraction of~$G$ along~$e$} produces a multigraph $G/e=(V',E',M')$ such that: $$\eqalign{ @@ -60,7 +60,7 @@ m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr Sometimes we need contraction for simple graphs as well. It corresponds to performing the multigraph contraction, unifying parallel edges and deleting loops. -\defn\thmid{simpcont}% +\defn\id{simpcont}% Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction of~$G$ along~$e$} produces a graph $G.e=(V',E')$ such that: $$\eqalign{ -- 2.39.2