From 45c3472ad54cd6ceef01c44a07d71b97e9fe3eb9 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 22 Feb 2008 17:52:54 +0100 Subject: [PATCH] Extended the chapter on minors. --- PLAN | 1 + adv.tex | 101 ++++++++++++++++++++++++++++++++++++++++++++++----- biblio.bib | 11 ++++++ mst.tex | 6 +-- notation.tex | 13 +++++++ 5 files changed, 120 insertions(+), 12 deletions(-) diff --git a/PLAN b/PLAN index 0c0851e..8039758 100644 --- a/PLAN +++ b/PLAN @@ -56,6 +56,7 @@ Spanning trees: - Euclidean MST - Some algorithms (most notably Fredman-Tarjan) do not need flattening - reference to mixed Boruvka-Jarnik +- use the notation for contraction by a set Models: diff --git a/adv.tex b/adv.tex index e137a29..f4dc358 100644 --- a/adv.tex +++ b/adv.tex @@ -12,9 +12,9 @@ Can we find any broader class of graphs where the algorithm is still efficient? The right context turns out to be the minor-closed graph classes, which are closed under 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 simple graph contractions (see \ref{simpcont}). +\defn\id{minordef}% +A~graph~$H$ is a \df{minor} of a~graph~$G$ (written as $H\minorof G$) iff it can be obtained +from a~subgraph of~$G$ by a sequence of simple graph contractions (see \ref{simpcont}). \defn A~class~$\cal C$ of graphs is \df{minor-closed}, when for every $G\in\cal C$ and @@ -22,23 +22,106 @@ its every minor~$H$, the graph~$H$ lies in~$\cal C$ as well. A~class~$\cal C$ is \df{non-trivial} if at least one graph lies in~$\cal C$ and at least one lies outside~$\cal C$. \example -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 notably the linearity of the number of edges. +Non-trivial minor-closed classes include: +\itemize\ibull +\:planar graphs, +\:graphs embeddable in any fixed surface (i.e., graphs of bounded genus), +\:graphs embeddable in~${\bb R}^3$ without knots or without interlocking cycles, +\:graphs of bounded tree-width or path-width. +\endlist + +\para +Many of the nice structural properties of planar graphs extend to +minor-closed classes, too (see \cite{diestel:gt} for a~nice overview +of this theory). The most important property is probably the characterization +of such classes by forbidden minors. + +\defn +For a~class~$\cal H$ of graphs we define $\Forb({\cal H})$ as the class +of graphs which do not contain any of the graphs in~$\cal H$ as a~minor. +We will call $\cal H$ the set of \df{forbidden (or excluded) minors} for this class. + +\obs +For every~${\cal H}\ne\emptyset$, the class $\Forb({\cal H})$ is non-trivial +and closed on minors. This works in the opposite direction as well: for every +minor-closed class~$\cal C$ there is a~class $\cal H$ such that ${\cal C}=\Forb({\cal H})$. +One such~$\cal H$ is the complement of~$\cal C$, but smaller sets can be found, too. +For example, the planar graphs exclude exactly $K_5$ and~$K_{3,3}$ --- this follows +from the Kuratowski's theorem (the theorem uses forbidden subdivisions, but while +in general this is not the same as forbidden minors, it is for $K_5$ and $K_{3,3}$). +The celebrated theorem by Robertson and Seymour guarantees that we can always find +a~finite set of forbidden minors. + +\thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}} +For every non-trivial minor-closed graph class~$\cal C$ there exists +a~finite set~$\cal H$ of graphs such that ${\cal C}=\Forb({\cal H})$. + +\proof +This theorem has been proven in the series of papers on graph minors +culminating with~\cite{rs:wagner}. See this paper and follow the references +to the previous articles in the series. +\qed + +\para +We will make use of another important property --- the bounded density of minor-closed +classes. The connection between minors and density dates back to Mader in the 1960's +and it can be proven without use of the Robertson-Seymour theorem. \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 $m(G) \le \varrho\cdot n(G)$ holds for every $G\in\cal C$. +\thmn{Mader \cite{mader:dens}} +For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph +with average degree at least~$h(k)$ contains a~subdivision of~$K_{k}$ as a~subgraph. + +\proofsketch +(See Lemma 3.5.1 in \cite{diestel:gt} for a~complete proof in English.) + +Let us fix~$k$ and prove by induction on~$m$ that every graph with average +degree $a\ge 2^m$ contains a~subdivision of some graph with $k$~vertices +and ${k\choose 2}\ge m\ge k$~edges. For $m={k\choose 2}$ the theorem follows +as the only graph with~$k$ vertices and~$k\choose 2$ edges is~$K_k$. + +The base case $m=k$: Let us observe that when the average degree +is~$a$, removing any vertex of degree less than~$a/2$ does not decrease the +average degree. A~graph with $a\ge 2^k$ therefore has a~subgraph +with minimum degree $\delta\ge a/2=2^{k-1}$. Such subgraph contains +a~cycle on more than~$\delta$ vertices, in other words a~subdivision of +the cycle~$C_k$. + +Induction step: Let~$G$ be a~graph with average degree at least~$2^m$ and +assume that the theorem already holds for $m-1$. Without loss of generality, +$G$~is connected. Consider a~maximal set $U\subseteq V$ such that $G[U]$ is connected +and the graph $G.U$ ($G$~with $U$~contracted to a~single vertex) has average +degree at least~$2^m$ (such~$U$ exists, because $G=G.U$ whenever $\vert U\vert=1$). +Now consider the subgraph~$H$ induced in~$G$ by the +neighbors of~$U$. Every $v\in V(H)$ must have degree at least~$2^{m-1}$ +(otherwise we can add this vertex to~$U$, contradicting its maximality), so by +the induction hypothesis $H$ contains a~subdivision of some graph~$R$ with +$r$~vertices and $m-1$ edges. Any two non-adjacent vertices of~$R$ can be +connected in the subdivision by a~path lying entirely in~$G[U]$, which reveals +a~subdivision of a~graph on $m$~vertices. \qed + \thmn{Density of minor-closed classes, Mader~\cite{mader:dens}} -A~minor-closed class of graphs has finite edge density if and only if it is -a non-trivial class. +Every non-trivial minor-closed class of graphs has finite edge density. \proof -See Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalent conditions. +Let~$\cal C$ be any such class, $X$~its smallest excluded minor and $x=n(X)$. +As $H\minorof K_x$, the class $\cal C$ entirely lies in ${\cal C}'=\Forb(\{K_x\})$, so +$\varrho({\cal C}) \le \varrho({\cal C}')$ and therefore it suffices to prove the +theorem for classes excluding a~single complete graph~$K_x$. + +We will show that $\varrho({\cal C})\le 2h(x)$, where $h$~is the function +from the previous theorem. If any $G\in{\cal C}$ had more than $2h(x)\cdot n(G)$ +edges, its average degree would be at least~$h(x)$, so by the previous theorem +$G$~would contain a~subdivision of~$K_x$ and therefore $K_x$ as a~minor. \qed +\rem +See also Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalent conditions. + \thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}% For any fixed non-trivial minor-closed class~$\cal C$ of graphs, Algorithm \ref{contbor} finds the MST of any graph in this class in time $\O(n)$. (The constant hidden in the~$\O$ diff --git a/biblio.bib b/biblio.bib index 9be243d..697fd9d 100644 --- a/biblio.bib +++ b/biblio.bib @@ -753,3 +753,14 @@ inproceedings{ pettie:minirand, year={2006}, publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA} } + +@article{ rs:wagner, + title={{Graph minors: XX. Wagner's Conjecture}}, + author={Robertson, N. and Seymour, P. D.}, + journal={Journal of Combinatorial Theory Series B}, + volume={92}, + number={2}, + pages={325--357}, + year={2004}, + publisher={Academic Press, Inc. Orlando, FL, USA} +} diff --git a/mst.tex b/mst.tex index 5c67a72..6f0dea7 100644 --- a/mst.tex +++ b/mst.tex @@ -486,8 +486,8 @@ We will show a contractive version of the Bor\o{u}vka's algorithm in which these costs are carefully balanced, leading for example to a linear-time algorithm for MST in planar graphs. -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 +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 we will show that we can easily reduce the multigraph to a simple graph later. (See \ref{contract} for the exact definitions.) @@ -504,7 +504,7 @@ Then $G'$~has the same MST as~$G$. \proof Every spanning tree of~$G'$ is a spanning tree of~$G$. In the other direction: Loops can be never contained in a spanning tree. If there is a spanning tree~$T$ -containing a removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$ +containing a~removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$ for~$e$ makes~$T$ lighter. \qed \rem Removal of the heavier of a pair of parallel edges can be also viewed diff --git a/notation.tex b/notation.tex index 6c2a7d7..341f135 100644 --- a/notation.tex +++ b/notation.tex @@ -21,6 +21,7 @@ \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{$G[U]$}{subgraph induced by a~set $U\subset V(G)$} \n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$} \n{$\delta_G(v)$}{the edges of a one-vertex cut, i.e., $\delta_G(\{v\})$} \n{MST}{minimum spanning tree \[mstdef]} @@ -29,6 +30,7 @@ \n{$X \choose k$}{a set of all $k$-element subsets of a set~$X$} \n{$G/e$}{multigraph contraction \[contract]} \n{$G.e$}{simple graph contraction \[simpcont]} +\n{$G/X$, $G.X$}{contraction by a~set $X$ of vertices or edges \[setcont]} \n{$\alpha(n)$}{the inverse Ackermann's function} \n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$} \n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$} @@ -65,6 +67,9 @@ \n{$L(\pi,A)$}{lexicographic ranking function for permutations on a~set~$A\subseteq{\bb N}$ \[brackets]} \n{$L^{-1}(i,A)$}{lexicographic unranking function, the inverse of~$L$ \[brackets]} \n{$n^{\underline k}$}{the $k$-th falling factorial power: $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ \[kpranksect]} +\n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]} +\n{$K_k$}{the complete graph on~$k$ vertices} +\n{$C_k$}{the cycle on~$k$ vertices} } %-------------------------------------------------------------------------------- @@ -109,4 +114,12 @@ E' &= \{ \{m(x),m(y)\} ; xy\in E \land m(x)\ne m(y) \},\cr m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr }$$ +\defn\id{setcont}% +We can also extend the above definitions to contractions by a~set of vertices or edges. +For $F\subseteq E(G)$, the graph $G/F$ is defined as $(G/f_1)/f_2/\ldots/f_k$ where +$f_1,\ldots,f_k$ are the elements of~$F$ (you can observe that the result +does not depend on the order of edges). For $U\subseteq V(G)$, we define $G/U$ +as the graph with all vertices of~$U$ merged to a~single vertex, that is $(G\cup U^*)/U^*$, +where $U^*$ is the complete graph on~$U$. Similarly for $G.F$ and $G.U$. + \endpart -- 2.39.2