From 94677a788af967f14562dfd059ef37ec18a12fd3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 3 Jan 2012 18:00:43 +0100 Subject: [PATCH] Sekce o minorove uzavrenych tridach prepsana Uz vysvetluje, jak funguje odhad hustoty, jen chybi dukaz Maderovy vety. --- 6-borjar/6-borjar.tex | 95 +++++++++++++++++++++++++++++++++---------- ga.bib | 10 +++++ 2 files changed, 84 insertions(+), 21 deletions(-) diff --git a/6-borjar/6-borjar.tex b/6-borjar/6-borjar.tex index 92761e8..b241a21 100644 --- a/6-borjar/6-borjar.tex +++ b/6-borjar/6-borjar.tex @@ -48,40 +48,93 @@ P ne¾ jsou grafy rovinné. Tím správným universem jsou minorovì uzavøené tøídy: \s{Definice:} -Graf $H$ je {\I minorem} grafu $G$ (znaèíme $H \preceq G$) $\equiv$ $H$ lze z $G$ získat +Graf $H$ je {\I minorem} grafu $G$ (znaèíme $H \preceq G$), pokud lze $H$ získat z~$G$ mazáním vrcholù èi hran a kontrahováním hran (s~odstranìním smyèek a násobných hran). \s{Pozorování:} -$H \subseteq G \Rightarrow H \preceq G$. +Relace $\preceq$ je èásteèné uspoøádání na tøídì v¹ech grafù +(reflexivita a tranzitivita plynou pøímo z~definice, pro antisymetrii si staèí +v¹imnout, ¾e jak mazáním, tak kontrakcemi klesá souèet poètu vrcholù s~poètem hran). + +\s{Pozorování:} +Pokud je graf~$H$ podgrafem grafu~$G$, pak je také jeho minorem. +Opaènì to neplatí: napøíklad $C_3$ je minorem libovolné del¹í kru¾nice, +ale urèitì ne jejím podgrafem. \s{Definice:} -Tøída grafù $\cal C$ je {\I minorovì uzavøená} $\equiv \forall G,H: G \in {\cal C}, H \preceq G \Rightarrow H \in {\cal C}$. +Tøída grafù $\cal C$ je {\I minorovì uzavøená,} pokud kdykoliv $G\in {\cal C}$ +a $H\preceq G$, platí také $H \in {\cal C}$. + +\s{Pøíklady:} +Tøída v¹ech grafù a prázdná tøída jsou jistì minorovì uzavøené. Tìm øíkáme {\I triviální} +tøídy. Mezi ty netriviální patøí tøeba lesy, rovinné grafy, grafy nakreslitelné na dal¹í +plochy, grafy nakreslitelné do ${\bb R}^3$ tak, ¾e ¾ádná kru¾nice netvoøí uzel. -\s{Vìta:} (Robertson, Seymour) -Pokud je $\cal C$ minorovì uzavøená tøída grafù, existuje koneèná mno¾ina grafù $Z$ taková, -¾e pro ka¾dý graf $G$ platí: -$$G \not\in {\cal C} \iff \exists H \in Z: H \preceq G.$$ -Jinými slovy, ka¾dou minorovì uzavøenou tøídu lze charakterizovat {\I koneèným} poètem zakázaných minorù. +\def\Forb{{\rm Forb}} + +\s{Definice:} +Pro tøídu grafù ${\cal C}$ definujeme $\Forb({\cal C})$ jako tøídu v¹ech grafù, +jejich¾ minorem není ¾ádný graf z~${\cal C}$. Pro zjednodu¹ení znaèení budeme pro +koneèné tøídy psát $\Forb(G_1,\ldots,G_k)$ namísto $\Forb(\{G_1,\ldots,G_k\})$. + +\s{Pøíklady:} +$\Forb(K_1)$ je tøída v¹ech grafù, které neobsahují ¾ádnou hranu. +$\Forb(C_3)$ je tøída v¹ech lesù. +$\Forb(K_5,K_{3,3})$ jsou v¹echny rovinné grafy -- to je minorová analogie +Kuratowského vìty (pokud graf~$G$ obsahuje dìlení grafu~$H$, pak je $H\preceq G$; +opaènì to obecnì není pravda, ale zrovna pro dvojici $K_5$ a $K_{3,3}$ to funguje; +zkuste si sami). + +Lze ka¾dou minorovì uzavøenou tøídu~${\cal C}$ zapsat jako $\Forb({\cal F})$ +pro nìjakou tøídu~${\cal F}$ zakázaných minorù? Zajisté ano, staèí napøíklad +zvolit~${\cal F}$ jako doplnìk tøídy~${\cal C}$. Slavná Robertsonova-Seymourova +vìta \cite{rs:wagner} dokonce zaruèuje existenci {\I koneèné} tøídy zakázaných minorù. To není samo sebou, dokazuje se to dosti obtí¾nì (a~je to jedna z~nejslavnìj¹ích kombinatorických vìt za~posledních mnoho let), ale plyne z~toho spousta zajímavých dùsledkù. -Pìkné shrnutí této teorie najdete napøíklad v~Diestelove knize~\cite{diestel:gt}. +My si vystaèíme s~daleko jednodu¹¹ími prostøedky a zájemce o~hlub¹í studium minorové +teorie odká¾eme na Diestelovu knihu~\cite{diestel:gt}. + +Ve~zbytku této sekce doká¾eme následující vìtu, která je zobecnìním klasického +tvrzení o~hustotì rovinných grafù na minorovì uzavøené tøídy: -\s{Pozorování:} Napøíklad pro rovinné grafy jsou tìmi zakázanými minory právì -$K_{3,3}$ a $K_5$. To plyne z~Kuratowského vìty: jedna implikace je triviální, -druhá dá trochu práce: pokud je $K_{3,3} \preceq G$, najde se v~$G$ podgraf -isomorfní nìjakému dìlení~$K_{3,3}$; pokud je $K_5 \preceq G$, podgraf isomorfní -dìlení~$K_5$ se v~$G$ najít nemusí, ale pokud se nenajde, najde se tam podgraf isomorfní -dìlení $K_{3,3}$. (Zkuste si sami.) +\s{Definice:} {\I Hustotou} neprázdného grafu~$G$ nazveme $\varrho(G) = \vert E(G) \vert +/ \vert V(G) \vert$. Hustotou tøídy $\varrho(C)$ pak nazveme supremum z~hustot v¹ech +neprázdných grafù le¾ících v~této tøídì. -\s{Vìta:} (Robertson, Seymour) +\s{Vìta (o hustotì minorovì uzavøených tøíd):} Pokud je tøída grafù $\cal C$ minorovì uzavøená a netriviální (alespoò jeden graf v~ní le¾í -a alespoò jeden nele¾í), pak $\exists c > 0: \forall G \in {\cal C}: -\vert E(G) \vert \leq c\cdot \vert V(G) \vert$. +a alespoò jeden nele¾í), pak má koneènou hustotu. \s{Dùsledek:} -Jeliko¾ v¹echny grafy vygenerované pøedchozím algoritmem jsou minory grafu ze~vstupu, -mù¾eme pro odhad jejich hustoty pou¾ít pøedchozí vìtu a dostaneme lineární èasovou slo¾itost -dokonce pro ka¾dou netriviální minorovì uzavøenou tøídu grafù. +Pokud pou¾íváme kontrahující Borùvkùv algoritmus na grafy le¾ící v~nìjaké netriviální +minorovì uzavøené tøídì, pak v¹echny grafy, které algoritmus v~prùbìhu výpoètu sestrojí, +le¾í také v~této tøídì, tak¾e na odhad jejich hustoty mù¾eme pou¾ít pøedchozí vìtu. +Opìt vyjde, ¾e èasová slo¾itost algoritmu je lineární. + +\>{\I Dùkaz vìty:} +Uká¾eme nejprve, ¾e pro ka¾dou tøídu $\cal C$ existuje nìjaké~$k$ takové, ¾e +${\cal C} \subseteq \Forb(K_k)$. + +U¾ víme, ¾e ${\cal C}$ lze zapsat jako $\Forb({\cal F})$ pro nìjakou tøídu~${\cal F}$. +Oznaème~$F$ graf z~${\cal F}$ s~nejmen¹ím poètem vrcholù; pokud existuje více takových, +vybereme libovolný. Hledané~$k$ zvolíme jako poèet vrcholù tohoto grafu. + +Inkluze tvaru ${\cal A}\subseteq {\cal B}$ je ekvivalentní tomu, ¾e kdykoliv nìjaký graf~$G$ +nele¾í v~${\cal B}$, pak nele¾í ani v~${\cal A}$. Mìjme tedy nìjaký graf $G\not\in\Forb(K_k)$. +Proto $K_k \preceq G$. Ov¹em triviálnì platí $F\preceq K_k$ a relace \uv{být minorem} +je tranzitivní, tak¾e $F\preceq G$, a~proto $G\not\in {\cal C}$. + +Víme tedy, ¾e ${\cal C} \subseteq \Forb(K_k)$. Proto musí platit $\varrho({\cal C}) \le +\varrho(\Forb(K_k))$. Tak¾e postaèuje omezit hustotu tøíd s~jedním zakázaným minorem, +který je úplným grafem, a~to plyne z~následující Maderovy vìty. +\qed + +\s{Vìta (Maderova):} +Pro ka¾dé~$k\ge 2$ existuje $c(k)$ takové, ¾e kdykoliv má graf hustotu alespoò $c(k)$, +obsahuje jako podgraf nìjaké dìlení grafu~$K_k$. + +\proof +Viz Diestel \cite{diestel:gt}. \h{Jarníkùv algoritmus s Fibonacciho haldou} diff --git a/ga.bib b/ga.bib index 157daa2..8a6fc48 100644 --- a/ga.bib +++ b/ga.bib @@ -738,3 +738,13 @@ year={1999}, organization={ACM} } + +@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}, +} -- 2.39.2