From 2e180ebb8746bb441e5089764c627023ff34b62f Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Jan 2019 18:08:22 +0100 Subject: [PATCH] =?utf8?q?Planarita:=20D=C5=AFkaz=20korektnosti=20je=20sna?= =?utf8?q?d=20ji=C5=BE=20korektn=C3=AD?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit TODO: Obrázky --- 11-planar/11-planar.tex | 128 +++++++++++++++++++++++++--------------- 1 file changed, 79 insertions(+), 49 deletions(-) diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 03887f8..0abd22a 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -317,67 +317,97 @@ není rovinný. \proof Pro spor předpokládejme, že po~zpracování vrcholu~$v$ existuje nějaká zpětná hrana~$wv$, kterou algoritmus nenakreslil, čili že přístup z~$v$ k~$w$ je v~obou směrech blokován externími vrcholy. Rozborem případů ukážeme, -že tato situace vede ke~sporu buďto s~pravidly \#1 a \#2 nebo s~rovinností grafu. +že pokud jsme se důsledně řídili pravidly \#1 a \#2, graf není rovinný. + +Uvažme posloupnost bloků vedoucí od vrcholu~$v$ k~$w$. V~této posloupnosti se +musí vyskytovat nějaký blok~$B$, který má na obou stranách hranice aspoň jeden +externí vrchol -- jinak bychom totiž bloky popřeklápěli tak, abychom se dostali až do~$w$. + +{\I Nadřazené bloky.} +Nejprve ukážeme, že kořenem bloku~$B$ musí být přímo vrchol~$v$. Kdyby totiž +mezi~$v$ a~$B$ ležely nějaké další bloky, našli bychom v~grafu minor~$M$ z~následujícího +obrázku, který je isomorfní s~grafem $K_{3,3}$. Do vrcholu~$u$ jsme zkontrahovali +ještě nenakreslenou část grafu, do~$v$ všechny bloky ležící nad~$B$, do~$x$ a~$y$ +případné podřízené externí bloky (díky nimž se $x$ a~$y$ staly externími) a do~$w$ +všechny bloky ležící mezi~$B$ a~$w$. + +Blok~$B$ je tedy nejvyšší a přímo obsahuje vrchol~$v$. Této situaci odpovídá +minor~$N$, který je ovšem rovinný, takže na prokázání nerovinnosti grafu budeme +muset zkoumat vnitřek bloku. + +{\I Podřízené bloky.} +Předtím ale rozebereme případ, kdy vrchol~$w$ neleží přímo v~bloku~$B$, nýbrž +v~nějakém podřízeném bloku, který je připojen pod nějakou artikulaci $w'\in B$. +Tento podřízený blok přitom nemůže být externí: kdyby byl, najdeme v~grafu +minor XXXX obsahující $K_{3,3}$ (do~$w$ jsme zkontrahovali všechny podřízené +bloky mezi~$w'$ a~$w$). Pokud bychom tedy během obcházení hranice vstoupili do~$w'$, +pravidlo~\#2 by zaručilo, že dojdeme do~$w$ a díky pravidlu~\#1 bychom vzápětí +nakreslili hranu~$vw$. Tu jsme nenakreslili, takže jsme nedošli ani do~$w'$. +Můžeme tedy bez újmy na obecnosti předpokládat, že $w=w'$. + +{\I Existence plotu.} +Stačí se tedy omezit na situaci s~jediným blokem~$B$, v~němž leží vrcholy~$v$, $w$, +$x$ i~$y$. Dokážeme nyní, že uvnitř bloku existuje {\I plot} -- cesta mezi~$x$ +a~$y$, jejíž ostatní vrcholy neleží na hranici bloku. + +Předpokládejme pro spor, že plot neexistuje. Před nakreslením zpětných hran +vedoucích do~$v$ ještě blok~$B$ neexistoval a jeho vrcholy patřily do několika +menších bloků. Speciálně víme, že $w$~byla artikulace oddělující $x$ od~$y$, +takže každá cesta mezi~$x$ a~$y$ musela procházet přes~$w$. Proto v~pořadí podle DFS +musí ležet~$w$ před aspoň jedním z~vrcholů $x$ a~$y$. Tento vrchol tedy tehdy musel +ležet v~nějakém podřízeném bloku pod~$w$. A~z~nějakého takového bloku také musela +vést zpětná hrana (tehdy ještě externí) do~$v$, která později uzavřela blok~$B$. +K~této hraně jsme se tedy museli během obcházení dostat, a~to je možné pouze přes~$w$. + +{\I Nejvyšší plot.} +Plot tedy existuje. Zvolíme mezi všemi ploty ten nejvyšší, tedy nejbližší k~$v$ +(rozmyslete si, že to je v~rovinném nakreslení dobře definované). Označme $p_x$~vrchol, +v~němž se plot napojuje na cestu z~$v$ do~$w$ přes~$x$, a~obdobně~$p_y$. Rozmyslíme si, +jak může situace vypadat. + +{\bf A.} Předně žádný z~vrcholů $p_x$ a~$p_y$ nemůže být blíž k~$v$ než $x$ a~$y$. Pokud by +bez újmy na obecnosti $p_x$~ležel mezi $v$ a~$x$, našli bychom v~graf uminor AAA obsahující $K_{3,3}$: +cestu mezi $y$ a~$p_y$ jsme zkontrahovali do~$y$, celý plot jsme zkontrahovali do hrany~$p_xy$, +ostatní vrcholy jsou utvořeny stejně jako v~předchozích minorech. + +{\bf B.} Dále ukážeme, že plot může být připojen k~$v$ pouze přes $p_x$ a~$p_y$. V~opačném +případě by se v~grafu vyskytoval minor BBB obsahujicí $K_{3,3}$: do~$x$ jsme zkontrahovali +cestu mezi $x$ a~$p_x$, podobně do~$y$ cestu mezi $y$ a~$p_y$. + +{\bf C.} Nakonec se přesvědčíme, že na \uv{dolní} cestě z~$x$ do~$y$ přes~$w$ nemůže ležet +žádný externí vrchol. To by totiž způsobovalo minor CCC isomorfní s~$K_5$: +do~$w$ jsme zkontrahovali cestu mezi externím vrcholem a~$w$ a také všechny +případné podřízené bloky, v~nichž vede externí hrana. + +{\I Vnitřek bloku~$B$.} +Podívejme se, jak graf vypadal před nakreslením vrcholu~$v$. I~tehdy musel plot +společně s~dolní cestou ležet v~jednom bloku. Ten musel být z~jedné strany připojený +k~$v$ přes~$p_x$, z~druhé přes~$p_y$ (a~díky vlastnosti~{\bf B} nikudy jinudy). +Říkejme tomuto bloku~$B'$ a~označme $r_1\in\{p_x,p_y\}$ jeho kořen a $r_2$ druhý +z~vrcholů $p_x,p_y$. Nyní víme: -Označme $B$ blok, ve~kterém leží na~obou stranách hranice nějaké externí -vrcholy $x$ a~$y$ a pod nimi je připojen nějakou cestou vrchol~$w$. Takový blok -musí určitě existovat, protože jinak by algoritmus všechny bloky na~cestě z~$v$ do~$w$ -popřeklápěl tak, aby se hrana $wv$ vešla. V~grafu se tedy musí vyskytovat jeden -z~následujících minorů (do~vrcholu~$u$ jsme kontrahovali celou dosud nenakreslenou část grafu; -vybarvená část odpovídá vnitřku bloku; hranaté vrcholy jsou externí): +\itemize\ibull +\:Díky {\bf A:} $r_2$~je předkem $x$ nebo~$y$ (případně je takovému vrcholu roven), +takže je při vstupu do~$r_1$ externí. +\:Díky {\bf B:} jdeme-li po plotu z~$r_1$, nejbližší \uv{zajímavý} vrchol bude~$r_2$. +\:Díky {\bf C:} žádný vrchol na dolní cestě není externí. +\endlist + +Při vstupu~$r_1$ tedy plot vede k~externími vrcholu, zatímco dolní cesta +k~internímu. Podle pravidla \#2 si tedy algoritmus vybere dolní cestu, kde ho +nic nezastaví, takže dojde až do~$w$ a~nakreslí zpětnou hranu $vw$. +\qed \bigskip \centerline{\putepdf{}{minor1.epdf}\qquad\putepdf{}{minor2.epdf}} \bigskip -Minor~$M$ přitom odpovídá situaci, kdy $v$ neleží v~bloku~$B$. Tento případ -snadno vyloučíme, protože $M$ je isomorfní s~grafem $K_{3,3}$. V~grafu se proto -musí vyskytovat~$N$. Tento minor je ale rovinný, takže musíme ukázat, že vnitřek -bloku brání nakreslení hrany~$vw$ dovnitř. Vždy pak dojdeme k~některému z~následujících -nerovinných minorů ($N_1$ až $N_3$ jsou isomorfní s~$K_{3,3}$ a $N_4$ s~$K_5$): - \bigskip \centerline{\putepdf{}{minor3.epdf}\qquad\putepdf{}{minor4.epdf}} \bigskip \centerline{\putepdf{}{minor5.epdf}\qquad\putepdf{}{minor6.epdf}} \bigskip -\>Uvažme, jak bude $B$ vypadat po~odebrání vrcholu~$v$ a hran z~něj vedoucích: - -\numlist\nalpha -\:{\I přestane být 2-souvislý} -- tehdy se zaměříme na~bloky ležící na~cestě~$xy$: - -\numlist\nparen -\finalfix{\rightskip=0.5\rightskip} -\:{\I $w$ je artikulace} na této cestě -- BÚNO je taková artikulace v~DFS prohledána po~bloku obsahujícím~$x$, -ale před~$y$. Tehdy nám jistě $x$ nezabránilo v~tom, abychom do~$w$ došli (může blokovat -jenom jednu stranu hranice), takže jsme se ve~$w$ museli rozhodnout, že přednostně zpracujeme -pokračování cesty do~$y$ před hranou~$vw$, a~to je spor s~pravidlem~\#1. - -\:{\I $w$ je v~bloku připojeném pod takovou artikulací} -- aby se pravidlo~\#1 vydalo -do~$y$ místo podřízených bloků, musí být alespoň jeden z~nich externí, -takže v~$G$ je minor~$N_1$. - -\:{\I $w$ je v~bloku na~cestě nebo připojen pod takový blok} -- opět si všimneme, že do~bloku jsme -vstoupili mezi~$x$ a~$y$. Abychom se podle pravidla~\#2 rozhodli pro stranu, z~níž nevede -hrana~$vw$, musela na~druhé straně být také hrana do~$v$, a~proto se v~grafu vyskytuje minor~$M$. -\endlist - -\:{\I zůstane 2-souvislý} a vznikne z~něj nějaký blok~$B'$ -- tehdy rozebereme, jaké hrany vedou mezi $v$ a $B'$: - -\numlist\nparen -\finalfix{\rightskip=0.5\rightskip} -\:{\I více než dvě hrany} -- minor~$N_2$. -\:{\I alespoň jedna hrana na \uv{horní} cestu} (to jest na~tu, na~niž neleží~$w$) -- minor~$N_3$. -\:{\I dvě hrany do~$x,y$ nebo na \uv{dolní} cestu} -- ať už jsme vstoupili na~hranici bloku~$B'$ -kteroukoliv hranou, pravidlo~\#2 nám řeklo, že máme pokračovat vrchem, což je možné jedině tehdy, -je-li na~spodní cestě ještě jeden externí vrchol, a~to dává minor~$N_4$. -\qeditem - -\endlist - -\endlist - \s{Poznámka:} Podle tohoto důkazu bychom také mohli v~lineárním čase v~každém nerovinném grafu nalézt Kuratowského podgraf, dokonce také v~$O(n)$, jelikož když je $m>3n-6$, můžeme se omezit na~libovolných $3n-5$ hran, které určitě tvoří nerovinný podgraf. -- 2.39.2