11-planar/11-planar.tex

   1 \input ../sgr.tex
   2
   3 \prednaska{11}{Rovinné grafy}{}
   4
   5 Rovinné grafy se objevují v~nejrùznìj¹ích praktických aplikacích teorie grafù,
   6 a~tak okolo nich vyrostlo znaèné mno¾ství algoritmù. I~kdy¾ existují výjimky,
   7 jako napøíklad ji¾ zmínìné hledání kostry rovinného grafu, vìt¹ina takových
   8 algoritmù pracuje s~konkrétním vnoøením grafu do~roviny (rovinným nakreslením).
   9
  10 Proto se zamìøíme na~algoritmus, který zadaný graf buïto vnoøí do~roviny, nebo se
  11 zastaví s~tím, ¾e graf není rovinný. Tarjan ji¾ v~roce 1974 ukázal \cite{tarjan:planarity},
  12 ¾e je to mo¾né provést v~lineárním èase, ale jeho algoritmus je ponìkud
  13 komplikovaný. Od~té doby se objevilo mnoho zjednodu¹ení, prozatím vrcholících
  14 algoritmem Boyera a Myrvoldové \cite{boyer:cutting}, a ten zde uká¾eme.
  15
  16 Jakmile u¾ nìjaké rovinné nakreslení máme, lze z~nìj celkem snadno vytváøet
  17 rovinná nakreslení s~rùznými speciálními vlastnostmi. Za~zmínku stojí napøíklad
  18 Schnyderùv algoritmus \cite{schnyder:grid} generující v~lineárním èase nakreslení,
  19 v~nìm¾ v¹echny hrany jsou úseèky a vrcholy le¾í v~møí¾ových bodech møí¾ky $(n-2)\times (n-2)$,
  20 a~o~nìco jednodu¹¹í algoritmus \cite{chrobak:grid} kreslící do~møí¾ky $(2n-4)\times (n-2)$.
  21
  22 Tak s~chutí do toho \dots
  23
  24 \h{DFS a bloky}
  25
  26 Pøipomeòme si nejprve nìkteré vlastnosti prohledávání do~hloubky (DFS) a jeho pou¾ití
  27 k~hledání komponent vrcholové 2-souvislosti {\I (blokù).}
  28
  29 \s{Definice:} Prohledávání do~hloubky rozdìlí $E$ na~ètyøi druhy hran: {\I stromové} (po~nich¾
  30 DFS pro¹lo a rekurzivnì se zavolalo; tyto hrany vytváøejí {\I DFS strom} orientovaný z~koøene),
  31 {\I zpìtné} (vedou do~vrcholu na~cestì mezi prohledávaným vrcholem a koøenem,
  32 èili do~takového, který se právì nachází na~zásobníku, a~v~tomto smìru si je zorientujeme),
  33 {\I dopøedné} (vedou do~ji¾ zpracovaného vrcholu le¾ícího v~DFS stromu pod aktuálním vrcholem)
  34 a zbývající {\I pøíèné} (z~tohoto vrcholu do~jiného podstromu).
  35
  36 \s{Lemma:} Prohledáváme-li do~hloubky neorientovaný graf, nevzniknou ¾ádné dopøedné ani
  37 pøíèné hrany.\foot{Pro úplnost: v~orientovaném grafu mohou existovat dopøedné
  38 a také pøíèné vedoucí \uv{zprava doleva}, tedy do~døíve nav¹tíveného podstromu.}
  39
  40 \s{Lemma:} Relace \uv{Hrany $e$ a $f$ le¾í na~spoleèné kru¾nici} (znaèíme $e\sim f$) je ekvivalence. Její
  41 tøídy tvoøí maximální 2-souvislé podgrafy (bloky). Vrchol $v$ je artikulace právì tehdy,
  42 sousedí-li s~ním hrany z~více blokù.
  43
  44 Pokud spustíme na~graf DFS, je pøirozené testovat, do~jakých blokù patøí stromové
  45 hrany sousedící s~právì prohledávaným vrcholem~$v$: stromová hrana $uv$, po~které jsme
  46 do~$v$ pøi¹li, a hrany $vw_1$ a¾ $vw_k$ vedoucí do~podstromù $T_1$ a¾ $T_k$ (zpìtné hrany
  47 jsou v¾dy ekvivalentní s~hranou $uv$). Pokud je $uv \sim vw_i$, musí existovat cesta
  48 z~podstromu $T_i$ do~vrcholu~$u$, která nepou¾ije právì testované hrany. Taková cesta
  49 ale mù¾e podstrom opustit pouze zpìtnou hranou (stromová je zakázaná a dopøedné ani pøíèné
  50 neexistují). Jinými slovy $uv\sim vw_i$ právì tehdy, kdy¾ existuje zpìtná hrana z~podstromu~$T_i$
  51 do~vrcholu $u$ nebo blí¾e ke~koøeni.
  52
  53 Pokud nìkterá dvojice $vw_i$, $vw_j$ není ekvivalentní pøes hranu $uv$ (nebo pokud hrana $uv$
  54 ani neexistuje, co¾ se nám v~koøeni DFS stromu mù¾e stát), le¾í v~rùzných blocích, proto¾e
  55 $T_i$ a $T_j$ mohou být spojeny jen pøes své koøeny (pøíèné hrany neexistují). Ze~zpìtných
  56 hran tedy získáme kompletní strukturu blokù.
  57
  58 Nyní si staèí rozmyslet, jak existenci zpìtných hran testovat rychle. K~tomu se bude hodit:
  59
  60 \s{Definice:} Je-li $v$ vrchol grafu, pak:
  61 \itemize\ibull
  62 \:$\<Enter>(v)$ udává poøadí, v~nìm¾ prohledávání do~vrcholu~$v$ vstoupilo.
  63 \:$\<Ancestor>(v)$ je nejmen¹í z~\<Enter>ù vrcholù, do~nich¾ vede z~$v$ zpìtná hrana.
  64 \:$\<LowPoint>(v)$ je minimum z~\<Ancestor>ù vrcholù le¾ících v~podstromu pod~$v$.
  65 \endlist
  66
  67 \s{Pozorování:} \<Enter>, \<Ancestor> i \<Lowpoint> v¹ech vrcholù lze spoèítat
  68 bìhem prohledávání, tedy také v~lineárním èase.
  69
  70 Rozpoznávání blokù a artikulací mù¾eme shrnout do~následujícího lemmatu:
  71
  72 \s{Lemma:}
  73 Stromové hrany $uv$ a $vw$ le¾í v~tomté¾ bloku ($uv\sim vw$) právì
  74 tehdy, kdy¾ $\<LowPoint>(w) < \<Enter>(v)$. Vrchol~$v$ je artikulace právì
  75 tehdy, kdy¾ nìkterý z~jeho synù $w$ má $\<LowPoint>(w) \ge \<Enter>(v)$.
  76
  77 \h{Postup kreslení}
  78
  79 Graf budeme kreslit v~opaèném poøadí oproti DFS, tj. od~nejvìt¹ích \<Enter>ù k~nejmen¹ím,
  80 a v¾dy si budeme udr¾ovat blokovou strukturu ji¾ nakreslené èásti grafu, uspoøádanou
  81 podle DFS stromu -- ka¾dý blok bude mít svùj koøen, s~výjimkou nejvy¹¹ího bloku
  82 je tento koøen souèasnì artikulací v~nadøazeném bloku. Aby se nám tato situace snadno
  83 reprezentovala, mù¾eme artikulace naklonovat a ka¾dý blok pak dostane svou vlastní
  84 kopii artikulace.
  85
  86 Také budeme vyu¾ívat toho, ¾e nakreslení ka¾dého bloku, který není
  87 most, je ohranièeno kru¾nicí, a mosty zdvojíme, aby to pro nì platilo
  88 také. Navíc v~libovolném nakreslení mù¾eme kterýkoliv blok spolu se v¹emi bloky
  89 le¾ícími pod~ním pøeklopit podle koøenové artikulace, ani¾ bychom poru¹ili
  90 rovinnost.
  91
  92 V¹imnìme si, ¾e pokud vede z~nìjakého u¾ nakresleného vrcholu je¹tì nenakreslená hrana,
  93 lze pokraèovat po~nenakreslených hranách a¾ do~koøene DFS stromu. V¹echny vrcholy, ke~kterým
  94 je¹tì bude potøeba nìco pøipojit (takovým budeme øíkat {\I externì aktivní} a za~chvíli
  95 to nadefinujeme formálnì), proto musí le¾et v~té¾e stìnì dosud nakresleného
  96 podgrafu a bez újmy na~obecnosti si vybereme, ¾e to bude vnìj¹í stìna.
  97
  98 Základním krokem algoritmu tedy bude roz¹íøit nakreslení o~nový
  99 vrchol~$v$ a o~v¹echny hrany vedoucí z~nìj do~jeho (ji¾ nakreslených)
 100 DFS-následníkù.  Stromové hrany pùjdou nakreslit v¾dy, pøidáme je jako
 101 triviální bloky (2-cykly) a nejsou-li to mosty, brzy se nìjakou
 102 zpìtnou hranou spojí s~jinými bloky. Zpìtné hrany byly a¾ donedávna
 103 externì aktivní, tak¾e pøidání jedné zpìtné hrany nahradí cestu
 104 po~okraji bloku touto hranou (tím vytvoøí novou stìnu) a také mù¾e
 105 slouèit nìkolik blokù do~jednoho:
 106
 107 \figure{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize}
 108 \figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externì aktivní vrcholy)}{\epsfxsize}
 109
 110 Bude se nám hodit, ¾e èas potøebný na~tuto operaci je pøímo úmìrný poètu
 111 hran, které ubyly z~vnìj¹í stìny, co¾ je amortizovanì konstanta.
 112
 113 Mù¾e se nám ale stát, ¾e zpìtná hrana zakryje nìjaký externì aktivní vrchol.
 114 Tehdy musíme nìkteré bloky pøeklopit tak, aby externì aktivní vrcholy
 115 zùstaly venku. Potøebujeme tedy datové struktury, pomocí nich¾ bude mo¾né
 116 pøeklápìt efektivnì a co víc, také rychle poznávat, kdy je pøeklápìní potøebné.
 117
 118 \h{Externí aktivita}
 119
 120 Jestli¾e z~nìjakého vrcholu~$v$ bloku~$B$ vede dosud nenakreslená hrana, musí
 121 být tento vrchol na~vnìj¹í stìnì, tak¾e musí také zùstat na~vnìj¹í stìnì
 122 i~vrchol, pøes který je~$B$ pøipojen ke~zbytku grafu. Proto externí aktivitu
 123 nadefinujeme tak, aby pokrývala i tyto pøípady:
 124
 125 \s{Definice:} Vrchol~$w$ je {\I externì aktivní} pokud buïto z~$w$ vede zpìtná
 126 hrana do~je¹tì nenakresleného vrcholu, nebo je pod~$w$ pøipojen externì aktivní
 127 blok, èili blok obsahující alespoò jeden externì aktivní vrchol.
 128
 129 Jinými slovy vrchol $w$ je externì aktivní pøi zpracování vrcholu~$v$, pakli¾e $\<Ancestor>(w) < \<Enter>(v)$,
 130 nebo pokud pro nìkterého ze~synù $x$ le¾ícího v~jiném bloku je $\<LowPoint>(x) < \<Enter>(v)$.
 131 Druhá podmínka funguje díky tomu, ¾e koøen bloku má v~tomto bloku právì jednoho syna
 132 (jinak by existovala pøíèná hrana, co¾ víme, ¾e není pravda), tak¾e minimum z~\<Ancestor>ù
 133 v¹ech vrcholù le¾ících uvnitø bloku je pøesnì \<LowPoint> tohoto syna.
 134 Ve~statickém grafu by se v¹echny testy redukovaly na~$\<LowPoint>(w)$, nám se ov¹em bloková
 135 struktura prùbì¾nì mìní, tak¾e musíme uva¾ovat bloky v~souèasném okam¾iku. Proto si zavademe:
 136
 137 \s{Definice:} $\<BlockList>(w)$ je seznam v¹ech blokù pøipojených v~daném okam¾iku
 138 pod vrcholem~$w$, reprezentovaných jejich koøeny (klony vrcholu~$w$) a jedinými syny koøenù.
 139 Tento seznam udr¾ujeme setøídìný vzestupnì podle $\<LowPoint>$ù synù.
 140
 141 \s{Lemma:} Vrchol~$w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud je buïto $\<Ancestor>(w) < \<Enter>(v)$,
 142 nebo první prvek seznamu $\<BlockList>(w)$ má $\<LowPoint> < \<Enter>(v)$. Navíc
 143 seznamy \<BlockList> lze udr¾ovat v~amortizovanì konstantním èase.
 144
 145 \proof První èást plyne z~definice. V¹echny seznamy na~zaèátku bìhu algoritmu
 146 sestrojíme v~lineárním èase pøihrádkovým tøídìním a kdykoliv slouèíme blok
 147 s~nadøazeným blokem, odstraníme ho ze~seznamu v~pøíslu¹né artikulaci.
 148 \qed
 149
 150 \h{Reprezentace blokù a pøeklápìní}
 151
 152 Pro ka¾dý blok si potøebujeme pamatovat vrcholy, které le¾í na~hranici
 153 (nìkteré z~nich jsou externì aktivní, ale to u¾ umíme poznat) a bloky,
 154 které jsou pod nimi pøipojené. Dále je¹tì vnitøní strukturu bloku vèetnì
 155 uvnitø pøipojených dal¹ích blokù, ale jeliko¾ ¾ádné vnitøní vrcholy nejsou
 156 externì aktivní, vnitøek u¾ neovlivní dal¹í výpoèet a potøebujeme jej pouze
 157 pro vypsání výstupu.
 158
 159 Pro na¹e úèely bude staèit zapamatovat si u~ka¾dého bloku, jestli je
 160 oproti nadøazenému bloku pøeklopen. Tuto informaci zapí¹eme do~koøene
 161 bloku. Ka¾dý vrchol na~hranici bloku pak bude obsahovat dva~ukazatele
 162 na~sousední vrcholy. Neumíme sice lokálnì poznat, který ukazatel odpovídá
 163 kterému smìru, ale kdy¾ se nìjakým smìrem vydáme, doká¾eme ho dodr¾et
 164 -- staèí si v¾dy vybrat ten ukazatel, který nás nezavede do~právì
 165 opu¹tìného vrcholu.
 166
 167 Ka¾dý vrchol si také bude pamatovat seznam svých sousedù,
 168 podle orientace bloku buïto v~hodinkovém nebo opaèném poøadí.
 169 Chceme-li pøidat hranu, potøebujeme tedy znát absolutní orientaci,
 170 ale to pùjde snadno, jeliko¾ hrany pøidáváme jen k~vrcholùm na~hranici,
 171 poté co k~nim po~hranici dojdeme z~koøene.
 172
 173 K~pøeklopení bloku vèetnì v¹ech podøízených blokù nám staèí invertovat
 174 bit v~koøeni, pokud chceme pøeklopit jen tento blok, invertujeme bity
 175 i v~koøenech v¹ech podøízených blokù, je¾ najdeme obcházením hranice.
 176
 177 Na~konci algoritmu spustíme post-processing, který v¹echny pøeklápìcí
 178 bity pøenese ve~smìru od~koøene k~potomkùm a urèí tak absolutní orientaci
 179 v¹ech seznamù.
 180
 181 \h{®ivý podgraf}
 182
 183 Kdy¾ nakreslíme nový vrchol~$v$ a z~nìj vedoucí stromové hrany, musíme obejít
 184 ka¾dý podstrom, ve~vhodném poøadí nakreslit zpìtné hrany do~$v$ a podle
 185 potøeby pøeklopit bloky. V~podstromu ov¹em mù¾e být mnoho blokù, které
 186 ¾ádnou pozornost nevy¾adují a bìh algoritmu by zbyteènì brzdily.
 187 Proto podobnì jako externí aktivitu nadefinujeme je¹tì
 188 ¾ivost vrcholu a ta bude odpovídat zpìtným hranám vedoucím do~$v$.
 189
 190 \s{Definice:}
 191 Vrchol~$w$ je {\I ¾ivý,} pokud z~nìj buïto vede zpìtná hrana do~právì
 192 zpracovávaného vrcholu~$v$, nebo pokud pod ním je pøipojen ¾ivý blok,
 193 tj. blok obsahující ¾ivý vrchol. Není-li ¾ivý vrchol èi blok externì aktivní,
 194 budeme mu øíkat {\I internì aktivní.} Pakli¾e není vrchol/blok ani ¾ivý, ani externì aktivní,
 195 budeme ho nazývat {\I neaktivní.}
 196
 197 Pøed procházením podstromù tedy nejprve probereme v¹echny zpìtné hrany vedoucí do~$v$
 198 a oznaèíme ¾ivé vrcholy. Pro ka¾dou zpìtnou hranu potøebujeme o¾ivit vrchol, z~nìj¾
 199 hrana vede, dále artikulaci, pod~ní¾ je tento blok pøipojen, a dal¹í artikulace
 200 na~cestì do~$v$. Poka¾dé, kdy¾ vstoupíme do~bloku (nìjakým vrcholem na~vnìj¹í stìnì),
 201 tedy potøebujeme nalézt koøen bloku. To udìláme tak, ¾e zaèneme obcházet vnìj¹í
 202 stìnu obìma smìry souèasnì, ne¾ dojdeme v~kterémkoliv smìru do~koøene. Navíc si v¹echny
 203 vrcholy, pøes nì¾ jsme pro¹li, oznaèkujeme a pøiøadíme k~nim rovnou ukazatel na~koøen,
 204 tudí¾ po~¾ádné èásti hranice neprojdeme vícekrát.\foot{Znaèky ani nebude potøeba
 205 mazat, kdy¾ si u nich poznamenáme, který vrchol byl koøenem v~okam¾iku, kdy jsme
 206 znaèku vytvoøili, a znaèky patøící ke~starým koøenùm budeme ignorovat, resp. pøepisovat.}
 207
 208 Výstupem této èásti algoritmu budou znaèky u~¾ivých vrcholù a u~artikulací
 209 také seznamy podøízených ¾ivých blokù. Tyto seznamy budeme udr¾ovat uspoøádané
 210 tak, aby externì aktivní bloky následovaly po~v¹ech internì aktivních. To nám
 211 usnadní práci v~hlavní èásti algoritmu.
 212
 213 \s{Lemma:} Pro ka¾dý koøen trvá znaèení ¾ivých vrcholù èas $\O(k+l)$, kde $k$ je poèet
 214 kreslených zpìtných hran a $l$ poèet vrcholù, které zmizely z~vnìj¹í stìny, èili
 215 amortizovaná konstanta.
 216
 217 \proof Alespoò polovina vrcholù, po~nich¾ jsme v~libovolném bloku pro¹li,
 218 zmizí z~vnìj¹í stìny, tak¾e hledání koøenù blokù trvá $\O(l)$. Pro ka¾dou zpìtnou
 219 hranu oznaèíme jeden vrchol jako ¾ivý a pak pokraèujeme hledáním koøenù.
 220 \qed
 221
 222 \h{Kreslení zpìtných hran}
 223
 224 Nyní ji¾ máme v¹e pøipraveno -- datové struktury, detekci externích vrcholù
 225 a oznaèování ¾ivého podgrafu -- a zbývá doplnit, jak algoritmus kreslí zpìtné
 226 hrany. Jeliko¾ zpìtné hrany vedoucí do~$v$ nemohou zpùsobit slouèení blokù
 227 le¾ících pod~$v$ (na~to jsou potøeba zpìtné hrany vedoucí nìkam nad~$v$ a ty
 228 je¹tì nekreslíme), zpracováváme ka¾dý podstrom zvlá¹». Pøidáme triviální blok
 229 pro stromovou hranu, pod nìj pøipojíme blokovou strukturu zatím nakreslené
 230 èásti podstromu a vydáme se po~hranici této struktury nejdøíve jedním
 231 a pak druhým smìrem.
 232
 233 Oba prùchody vypadají následovnì: Procházíme seznam vrcholù na~hranici a neaktivní
 234 vrcholy pøeskakujeme. Pokud objevíme ¾ivý vrchol, nakreslíme v¹e, co z~nìj vede,
 235 pøípadnì se zanoøíme do~¾ivých blokù, které jsou pøipojeny pod tímto vrcholem.
 236 Pokud objevíme externì aktivní vrchol (pøípadnì poté, co jsme ho o¹etøili jako ¾ivý),
 237 procházení zastavíme, proto¾e za externì aktivní vrchol ji¾ nemù¾eme po~této stranì
 238 hranice nic pøipojit, ani¾ by se externì aktivní vrchol dostal dovnitø nakreslení.
 239
 240 Pøitom se øídíme dvìma jednoduchými pravidly:
 241
 242 \s{Pravidlo \#1:} V~ka¾dém ¾ivém vrcholu zpracováváme nejdøíve zpìtné hrany do~$v$,
 243 pak podøízené internì aktivní bloky a koneènì podøízené externì aktivní bloky.
 244 (K~tomu se nám hodí, ¾e máme seznamy ¾ivých podøízených blokù setøídìné.)
 245
 246 \s{Pravidlo \#2:} Pokud vstoupíme do~dal¹ího bloku, vybereme si smìr, ve~kterém
 247 budeme pokraèovat, následovnì (pokud se li¹í od~smìru, ve~kterém zatím hranici
 248 obcházíme, blok pøeklopíme): preferujeme smìr k~internì
 249 aktivnímu vrcholu, pokud takový neexistuje, pak k~¾ivému externì aktivnímu
 250 vrcholu.
 251
 252 Èasová slo¾itost této èásti algoritmu je lineární ve~velikosti ¾ivého podgrafu
 253 a¾ na~dvì výjimky. Jednou je konec prohledávání od~posledního ¾ivého vrcholu
 254 k~bodu zastavení, druhou pak vybírání strany hranice pøi vstupu do~bloku.
 255 V~obou mù¾eme procházet a¾ lineárnì mnoho neaktivních vrcholù. Pomù¾eme si
 256 ov¹em snadno: kdykoliv projdeme souvislý úsek hranice tvoøený neaktivními
 257 vrcholy, pøidáme pomocnou hranu, která tento úsek pøeklene. Mù¾eme ji dokonce
 258 pøidat do~nakreslení a podrozdìlit si tak vnìj¹í stìnu.
 259
 260 \h{Hotový algoritmus}
 261
 262 Celý algoritmus tedy bude vypadat takto:
 263
 264 \algo
 265 \:Pokud má graf více ne¾ $3n-6$ vrcholù, odmítneme ho rovnou jako nerovinný.
 266 \:Prohledáme graf $G$ do~hloubky, spoèteme \<Enter,> \<Ancestor> a \<LowPoint> v¹ech vrcholù.
 267 \:Inicializujeme \<BlockList> v¹ech vrcholù.
 268 \:Procházíme vrcholy v~poøadí klesajících \<Enter>ù, pro ka¾dý vrchol~$v$:
 269 \::Nakreslíme v¹echny stromové hrany z~$v$ jako triviální bloky (2-cykly).
 270 \::Oznaèíme ¾ivý podgraf.
 271 \::Pro ka¾dého syna vrcholu~$v$ obcházíme ¾ivý podgraf nále¾ící k~tomuto vrcholu
 272    v~obou smìrech a kreslíme zpìtné hrany do~$v$.
 273 \::Zkontrolujeme, zda v¹echny zpìtné hrany vedoucí do~$v$ byly nakresleny, a pokud ne,
 274    prohlásíme graf za~nerovinný a zastavíme se.
 275 \:Projdeme hotové nakreslení do~hloubky a zorientujeme seznamy sousedù.
 276 \endalgo
 277
 278 \s{Vìta:} Tento algoritmus pro ka¾dý graf dobìhne v~èase $\O(n)$ a pokud byl graf rovinný,
 279 vydá jeho nakreslení, v~opaèném pøípadì ohlásí nerovinnost.
 280
 281 \proof První krok je korektní, jeliko¾ pro v¹echny rovinné grafy je $m\le 3n-6$; nadále
 282 tedy mù¾eme pøedpokládat, ¾e $m=\O(n)$. Lineární èasovou slo¾itost krokù 4--6 a~9 jsme ji¾
 283 diskutovali, kroky~7--8 jsou lineární ve~velikosti ¾ivého podgrafu, a tedy také $\O(n)$.
 284 Nakreslení vydané algoritmem je v¾dy rovinné a v¹echny stromové hrany jsou v¾dy
 285 nakresleny, zbývá tedy ukázat, ¾e zpìtnou hranu mù¾eme nenakreslit jen pokud
 286 graf nebyl rovinný. Tomu vìnujeme zbytek kapitoly.
 287 \qed
 288
 289 \h{Dùkaz korektnosti}
 290
 291 \s{Lemma:} Pokud existuje zpìtná hrana, kterou algoritmus nenakreslil, graf na~vstupu
 292 není rovinný.
 293
 294 \proof Pro spor pøedpokládejme, ¾e po~zpracování vrcholu~$v$ existuje nìjaká
 295 zpìtná hrana~$wv$, kterou algoritmus nenakreslil, èili ¾e pøístup z~$v$ k~$w$
 296 je v~obou smìrech blokován externì aktivními vrcholy. Rozborem pøípadù uká¾eme,
 297 ¾e tato situace vede ke~sporu buïto s~pravidly \#1 a \#2 nebo s~rovinností grafu.
 298
 299 Oznaème $B$ blok, ve~kterém le¾í na~obou stranách hranice nìjaké externì aktivní
 300 vrcholy $x$ a~$y$ a pod nimi je pøipojen nìjakou cestou vrchol~$w$. Takový blok
 301 musí urèitì existovat, proto¾e jinak by algoritmus v¹echny bloky na~cestì z~$v$ do~$w$
 302 popøeklápìl tak, aby se hrana $wv$ ve¹la. V~grafu se tedy musí vyskytovat jeden
 303 z~následujících minorù (do~vrcholu~$u$ jsme zkontrahovali celou dosud nenakreslenou èást grafu;
 304 vybarvená èást odpovídá vnitøku bloku; hranaté vrcholy jsou externì aktivní):
 305
 306 \bigskip
 307 \centerline{\epsfbox{minor1.eps}\qquad\epsfbox{minor2.eps}}
 308 \bigskip
 309
 310 Minor~$M$ pøitom odpovídá situaci, kdy $v$ nele¾í v~bloku~$B$. Tento pøípad
 311 snadno vylouèíme, proto¾e $M$ je isomorfní s~grafem $K_{3,3}$. V~grafu se proto
 312 musí vyskytovat~$N$. Tento minor je ale rovinný, tak¾e musíme ukázat, ¾e vnitøek
 313 bloku brání nakreslení hrany~$vw$ dovnitø. V¾dy pak dojdeme k~nìkterému z~následujících
 314 nerovinných minorù ($N_1$ a¾ $N_3$ jsou isomorfní s~$K_{3,3}$ a $N_4$ s~$K_5$):
 315
 316 \bigskip
 317 \centerline{\epsfbox{minor3.eps}\qquad\epsfbox{minor4.eps}}
 318 \bigskip
 319 \centerline{\epsfbox{minor5.eps}\qquad\epsfbox{minor6.eps}}
 320 \bigskip
 321
 322 \>Uva¾me, jak bude $B$ vypadat po~odebrání vrcholu~$v$ a hran z~nìj vedoucích:
 323
 324 \numlist\nalpha
 325 \:{\I pøestane být 2-souvislý} -- tehdy se zamìøíme na~bloky le¾ící na~cestì~$xy$:
 326
 327 \numlist\nparen
 328 \:{\I $w$ je artikulace} na této cestì -- BÚNO je taková artikulace v~DFS prohledána po~bloku obsahujícím~$x$,
 329 ale pøed~$y$. Tehdy nám jistì $x$ nezabránilo v~tom, abychom do~$w$ do¹li (mù¾e blokovat
 330 jenom jednu stranu hranice), tak¾e jsme se ve~$w$ museli rozhodnout, ¾e pøednostnì zpracujeme
 331 pokraèování cesty do~$y$ pøed hranou~$vw$, a~to je spor s~pravidlem~\#1.
 332
 333 \:{\I $w$ je v~bloku pøipojeném pod takovou artikulací} -- aby se pravidlo~\#1 vydalo
 334 do~$y$ místo podøízených blokù, musí být alespoò jeden z~nich externì aktivní,
 335 tak¾e v~$G$ je minor~$N_1$.
 336
 337 \:{\I $w$ je v~bloku na~cestì nebo pøipojen pod takový blok} -- opìt si v¹imneme, ¾e do~bloku jsme
 338 vstoupili mezi~$x$ a~$y$. Abychom se podle pravidla~\#2 rozhodli pro stranu, z~ní¾ nevede
 339 hrana~$vw$, musela na~druhé stranì být také hrana do~$v$, a~proto se v~grafu vyskytuje minor~$M$.
 340 \endlist
 341
 342 \:{\I zùstane 2-souvislý} a vznikne z~nìj nìjaký blok~$B'$ -- tehdy rozebereme, jaké hrany vedou mezi $v$ a $B'$:
 343
 344 \numlist\nparen
 345 \:{\I více ne¾ dvì hrany} -- minor~$N_2$.
 346 \:{\I alespoò jedna hrana na \uv{horní} cestu} (to jest na~tu, na~ni¾ nele¾í~$w$) -- minor~$N_3$.
 347 \:{\I dvì hrany do~$x,y$ nebo na \uv{dolní} cestu} -- a» u¾ jsme vstoupili na~hranici bloku~$B'$
 348 kteroukoliv hranou, pravidlo~\#2 nám øeklo, ¾e máme pokraèovat vrchem, co¾ je mo¾né jedinì tehdy,
 349 je-li na~spodní cestì je¹tì jeden externì aktivní vrchol, a~to dává minor~$N_4$.
 350 \qeditem
 351
 352 \endlist
 353
 354 \endlist
 355
 356 \s{Poznámka:} Podle tohoto dùkazu bychom také mohli v~lineárním èase v~ka¾dém nerovinném
 357 grafu nalézt Kuratowského podgraf, dokonce také v~$O(n)$, jeliko¾ kdy¾ je $m>3n-6$,
 358 mù¾eme se omezit na~libovolných $3n-5$ hran, které urèitì tvoøí nerovinný podgraf.
 359
 360 \references
 361 \bye