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}, který zde uká¾eme.
  15
  16 Jakmile 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¹¹í varianta \cite{chrobak:grid} do~møí¾ky $(2n-4)\times (n-2)$.
  21
  22 \h{DFS a bloky}
  23
  24 Pøipomeòme si nejprve nìkteré vlastnosti prohledávání do~hloubky (DFS) a jeho pou¾ití
  25 k~hledání komponent vrcholové 2-souvislosti {\I (blokù).}
  26
  27 \s{Definice:} Prohledávání do~hloubky rozdìlí $E$ na~ètyøi druhy hran: {\I stromové} (po~nich¾
  28 DFS pro¹lo a rekurzivnì se zavolalo; vytváøejí {\I DFS strom} orientovaný z~koøene),
  29 {\I zpìtné} (vedou do~vrcholu na~cestì mezi prohledávaným vrcholem a koøenem,
  30 èili do~takového, který se nachází na~zásobníku), {\I dopøedné} vedou do~ji¾ zpracovaného
  31 vrcholu le¾ícího v~DFS stromu pod aktuálním vrcholem a zbývající {\I pøíèné} (z~tohoto vrcholu
  32 do~jiného podstromu).
  33
  34 \s{Lemma:} Prohledáváme-li do~hloubky neorientovaný graf, nevzniknou ¾ádné dopøedné ani
  35 pøíèné hrany.\foot{Pro úplnost: v~orientovaném grafu mohou existovat dopøedné
  36 a také pøíèné vedoucí \uv{zprava doleva}, tedy døíve nav¹tívené komponenty.}
  37
  38 \s{Lemma:} Relace \uv{Hrany $e$ a $f$ le¾í na~spoleèné kru¾nici} (znaèíme $e\sim f$) je ekvivalence. Její
  39 tøídy tvoøí maximální 2-souvislé podgrafy (bloky). Vrchol $v$ je artikulace právì tehdy,
  40 sousedí-li s~ním hrany z~více blokù.
  41
  42 Pokud spustíme na~graf DFS, je pøirozené testovat, do~jakých blokù patøí stromové
  43 hrany sousedící s~právì prohledávaným vrcholem~$v$: stromová hrana $uv$, po~které jsme
  44 do~$v$ pøi¹li, a hrany $vw_1$ a¾ $vw_k$ vedoucí do~podstromù $T_1$ a¾ $T_k$ (zpìtné hrany
  45 jsou v¾dy ekvivalentní s~hranou $uv$). Pokud je $uv \sim vw_i$, musí existovat cesta
  46 z~podstromu $T_i$ do~vrcholu~$u$, která nepou¾ije právì testované hrany. Taková cesta
  47 ale mù¾e podstrom opustit pouze zpìtnou hranou (stromová je zakázaná a dopøedné ani pøíèné
  48 neexistují). Jinými slovy $uv\sim vw_i$ právì tehdy, kdy¾ existuje zpìtná hrana z~podstromu~$T_i$
  49 do~vrcholu $u$ nebo blí¾e ke~koøeni.
  50
  51 Pokud nìkterá dvojice $vw_i$, $vw_j$ není ekvivalentní pøes hranu $uv$ (nebo pokud hrana $uv$
  52 ani neexistuje, co¾ se nám v~koøeni DFS stromu mù¾e stát), le¾í v~rùzných blocích, proto¾e
  53 $T_i$ a $T_j$ mohou být spojeny jen pøes své koøeny (pøíèné hrany neexistují). Ze~zpìtných
  54 hran tedy získáme kompletní strukturu blokù.
  55
  56 Nyní si staèí rozmyslet, jak zpìtné hrany testovat efektivnì. K~tomu si zavedeme:
  57
  58 \s{Definice:} Pro vrchol $v$ zavedeme:
  59 \itemize\ibull
  60 \:$\<Enter>(v)$ udává poøadí, v~nìm¾ prohledávání do~vrcholu~$v$ vstoupilo.
  61 \:$\<Ancestor>(v)$ je nejmen¹í z~\<Enter>ù vrcholù, do~nich¾ vede z~$v$ zpìtná hrana.
  62 \:$\<LowPoint>(v)$ je minimum z~\<Ancestor>ù vrcholù le¾ících v~podstromu pod~$v$.
  63 \endlist
  64
  65 \s{Pozorování:} \<Enter>, \<Ancestor> i \<Lowpoint> v¹ech vrcholù lze spoèítat
  66 bìhem prohledávání, tedy také v~lineárním èase.
  67
  68 \s{Lemma:}
  69 Stromové hrany $uv$ a $vw$ le¾í v~tomté¾ bloku (tedy $uv\sim vw$) právì
  70 tehdy, kdy¾ $\<LowPoint>(w) < \<Enter>(v)$. Vrchol~$v$ je artikulace právì
  71 tehdy, kdy¾ nìkterý z~jeho synù $w$ má $\<LowPoint>(w) \ge \<Enter>(v)$.
  72
  73 \h{Postup kreslení}
  74
  75 Graf budeme kreslit v~opaèném DFS-poøadí, tj. od~nejvìt¹ích \<Enter>ù k~nejmen¹ím,
  76 a v¾dy si budeme udr¾ovat blokovou strukturu ji¾ nakreslené èásti grafu uspoøádanou
  77 podle DFS stromu -- ka¾dý blok bude mít svùj koøen a (mimo nejvy¹¹ího bloku)
  78 bude zavì¹en pod artikulací le¾ící v~nadøazeném bloku. Aby se nám tato
  79 situace snadno reprezentovala, mù¾eme artikulace naklonovat a ka¾dý blok
  80 pak dostane jednu kopii artikulace.
  81
  82 Také budeme vyu¾ívat toho, ¾e nakreslení ka¾dého bloku, který není
  83 most, je ohranièeno kru¾nicí, a mosty zdvojíme, aby to pro nì platilo
  84 také. Navíc libovolný blok spolu se v¹emi bloky le¾ícími pod~ním
  85 mù¾eme v~rovinì pøeklopit.
  86
  87 V¹imnìme si, ¾e pokud vede z~nìjakého u¾ nakresleného vrcholu~$v$ je¹tì nenakreslená hrana,
  88 lze pokraèovat po~nenakreslených hranách a¾ do~koøene. V¹echny vrcholy, ke~kterým
  89 je¹tì bude potøeba nìco pøipojit (takovým budeme øíkat {\I externì aktivní} a za~chvíli
  90 to nadefinujeme formálnì), tedy musí le¾et v~té¾e stìnì dosud nakresleného
  91 podgrafu a bez újmy na~obecnosti si vybereme, ¾e to bude vnìj¹í stìna.
  92
  93 Základním krokem algoritmu tedy bude roz¹íøit nakreslení o~nový vrchol~$v$,
  94 je-li v¹e v~DFS poøadí následující po~tomto vrcholu ji¾ nakresleno,
  95 a o~v¹echny s~ním incidentní hrany. Stromové hrany pùjdou nakreslit v¾dy,
  96 pøidáme je jako 2-cykly a a¾ se uká¾e, ¾e to nejsou mosty, pøipojíme
  97 je k~pøíslu¹nému bloku. Zpìtné hrany byly a¾ do~nedávna externì aktivní,
  98 tak¾e pøidání jedné zpìtné hrany nahradí cestu po~okraji bloku
  99 touto hranou (tím vytvoøí novou stìnu) a také mù¾e slouèit nìkolik
 100 blokù do~jednoho:
 101
 102 \twofigures{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize}{planar2.eps}{\dots\ po nìm}{\epsfxsize}
 103
 104 Bude se nám hodit, ¾e èas potøebný na~tuto operaci je pøímo úmìrný poètu
 105 hran, které ubyly z~vnìj¹í stìny, co¾ je amortizovanì konstanta.
 106
 107 Mù¾e se nám ale stát, ¾e zpìtná hrana zakryje nìjaký externì aktivní vrchol.
 108 Tehdy potøebujeme nìkteré bloky pøeklopit tak, aby externì aktivní vrcholy
 109 zùstaly venku. Potøebujeme tedy datové struktury, pomocí nich¾ bude mo¾né
 110 pøeklápìt efektivnì a co víc, také rychle poznat, kdy je pøeklápìní potøebné.
 111
 112 \h{Externí aktivita}
 113
 114 Pokud z~nìjakého vrcholu~$v$ bloku~$B$ vede dosud nenakreslená hrana, musí
 115 být tento vrchol na~vnìj¹í stìnì, tak¾e musí také zùstat na~vnìj¹í stìnì
 116 vrchol, pøes který je~$B$ pøipojen ke~zbytku grafu. Proto externí aktivitu
 117 nadefinujeme tak, aby pokrývala i tyto pøípady:
 118
 119 \s{Definice:} Vrchol~$w$ je {\I externì aktivní} pokud buïto z~$w$ vede zpìtná
 120 hrana do~je¹tì nenakresleného vrcholu, nebo je k~$w$ pøipojen externì aktivní
 121 blok, èili blok obsahující alespoò jeden externì aktivní vrchol. Externì
 122 aktivní vrcholy budeme kreslit jako ètvereèky.
 123
 124 Jinými slovy $w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud je $\<Ancestor>(w) < \<Enter>(v)$,
 125 nebo pokud pro nìkterého ze~synù $x$ le¾ícího v~jiném bloku je $\<LowPoint>(x) < \<Enter>(x)$.
 126 Ve~statickém grafu by staèilo testovat $\<LowPoint>(w)$, nám se ov¹em bloková
 127 struktura mìní, tak¾e musíme uva¾ovat bloky v~souèasném okam¾iku. Proto si zavademe:
 128
 129 \s{Definice:} $\<SepBlockList>(w)$ je seznam v¹ech synù vrcholu~$w$, které v~daném
 130 okam¾iku le¾í v~jiných blocích ne¾~$w$, setøídìný vzestupnì podle $\<LowPoint>$ù.
 131
 132 \s{Lemma:} Vrchol~$w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud buïto $\<Ancestor>(w) < \<Enter>(v)$,
 133 nebo první prvek $x$ seznamu $\<SepBlockList>(w)$ má $\<LowPoint>(x) < \<Enter>(v)$. Navíc
 134 seznamy \<SepBlockList> je mo¾no udr¾ovat v~amortizovanì konstantním èase.
 135
 136 \s{Dùkaz:} První èást plyne z~definice. V¹echny seznamy na~zaèátku bìhu algoritmu
 137 zkonstruujeme v~lineárním èase pøihrádkovým tøídìním a kdykoliv slouèíme blok
 138 s~koøenem~$x$ s~nadøazeným blokem, odstraníme $x$ ze~seznamu v~pøíslu¹né artikulaci.
 139 \qed
 140
 141 \h{Reprezentace blokù a pøeklápìní}
 142
 143 Pro ka¾dý blok si potøebujeme pamatovat vrcholy, které le¾í na~hranici
 144 (nìkteré z~nich jsou externì aktivní, ale to u¾ umíme poznat) a bloky,
 145 které jsou k~nim pøipojené. Dále je¹tì vnitøní strukturu bloku vèetnì
 146 uvnitø pøipojených dal¹ích blokù, ale jeliko¾ ¾ádné vnitøní vrcholy nejsou
 147 externì aktivní, vnitøek u¾ neovlivní dal¹í výpoèet a potøebujeme jej pouze
 148 pro vypsání výstupu.
 149
 150 Pro na¹e úèely bude staèit zapamatovat si u~ka¾dého bloku, jestli je
 151 oproti nadøazenému bloku pøeklopen. Tuto informaci zapí¹eme do~koøene
 152 bloku. Ka¾dý vrchol na~hranici bloku pak bude obsahovat dva~ukazatele
 153 na~sousední vrcholy. Neumíme sice lokálnì poznat, který ukazatel odpovídá
 154 kterému smìru, ale kdy¾ se nìjakým smìrem vydáme, doká¾eme ho dodr¾et
 155 -- staèí si v¾dy vybrat ten ukazatel, který nás nezavede do~vrcholu,
 156 z~nìj¾ jsme právì pøi¹li.
 157
 158 Ka¾dý vrchol bloku si také bude pamatovat seznam svých sousedù,
 159 podle orientace bloku buïto v~hodinkovém nebo opaèném poøadí.
 160 Chceme-li pøidat hranu, potøebujeme tedy znát abslolutní orientaci,
 161 ale to pùjde snadno, jeliko¾ hrany pøidáváme jen k~vrcholùm na~hranici
 162 a v¾dy k~nim po~hranici dojdeme z~koøene.
 163
 164 K~pøeklopení bloku vèetnì v¹ech podøízených blokù tedy staèí invertovat
 165 bit v~koøeni, pokud chceme pøeklopit jen tento blok, invertujeme bity
 166 i v~koøenech v¹ech podøízených blokù, které najdeme obcházením hranice.
 167
 168 Na~konci algoritmu spustíme post-processing, který v¹echny pøeklápìcí
 169 bity pøenese ve~smìru od~koøene k~potomkùm a urèí tak absolutní orientaci
 170 v¹ech seznamù.
 171
 172 \h{®ivý podgraf}
 173
 174 Kdy¾ nakreslíme nový vrchol~$v$ a z~nìj vedoucí stromové hrany, musíme obejít
 175 ka¾dý podstrom a ve~vhodném poøadí nakreslit zpìtné hrany do~$v$ a podle
 176 potøeby pøeklopit bloky. V~podstromu ov¹em mù¾e být mnoho blokù, které,
 177 aè jsou externì aktivní, ¾ádnou pozornost nevy¾adují a bìh algoritmu by
 178 zbyteènì brzdily. Proto podobnì jako externí aktivitu nadefinujeme je¹tì
 179 ¾ivost vrcholu, které bude odpovídat zpìtným hranám vedoucím do~$v$:
 180
 181 \s{Definice:}
 182 Vrchol~$w$ je {\I ¾ivý,} pokud z~nìj buïto vede zpìtná hrana do~právì
 183 zpracovávaného vrcholu~$v$, nebo pokud k~nìmu je pøipojen ¾ivý blok,
 184 tj. blok obsahující ¾ivý vrchol. Není-li ¾ivý vrchol èi blok externì aktivní,
 185 budeme mu øíkat {\I internì aktivní.} Pakli¾e není vrchol/blok ani ¾ivý, ani externì aktivní,
 186 budeme ho nazývat {\I neaktivní.}
 187
 188 Pøed procházením podstromù tedy nejprve probereme v¹echny zpìtné hrany vedoucí do~$v$
 189 a oznaèíme ¾ivé vrcholy. Pro ka¾dou zpìtnou hranu potøebujeme o¾ivit vrchol, z~nìj¾
 190 hrana vede, dále artikulaci, pod~ní¾ je tento blok pøipojen a dal¹í artikulace
 191 na~cestì do~$v$. Poka¾dé, kdy¾ vstoupíme do~bloku (nìjakým vrcholem na~vnìj¹í stìnì),
 192 tedy potøebujeme nalézt koøen bloku. To udìláme tak, ¾e zaèneme obcházet vnìj¹í
 193 stìnu obìma smìry souèasnì, ne¾ dojdeme v~jednom smìru do~koøene. Navíc si v¹echny
 194 vrcholy, pøes nì¾ jsme pro¹li, oznaèkujeme a pøiøadíme k~nim rovnou ukazatel na~koøen,
 195 tak¾e po~¾ádné èásti hranice neprojdeme vícekrát.\foot{Znaèky ani nebude potøeba
 196 mazat, kdy¾ si u nich poznamenáme, který vrchol byl koøenem v~okam¾iku, kdy jsme
 197 znaèku vytvoøili, a znaèky patøící ke~starým koøenùm budeme ignorovat, resp. pøepisovat.}
 198
 199 \s{Lemma:} Pro ka¾dý koøen trvá znaèení ¾ivých vrcholù èas $\O(k+l)$, kde $k$ je poèet
 200 kreslených zpìtných hran a $l$ poèet vrcholù, které zmizely z~vnìj¹í stìny, èili
 201 amortizovaná konstanta.
 202
 203 \s{Dùkaz:} Alespoò polovina vrcholù, po~nich¾ jsme v~libovolném bloku pro¹li,
 204 zmizí z~vnìj¹í stìny, tak¾e hledání koøenù blokù trvá $\O(l)$. Pro ka¾dou zpìtnou
 205 hranu oznaèíme jeden vrchol jako ¾ivý a pak pokraèujeme hledáním koøenù.
 206 \qed
 207
 208 \h{Kreslení zpìtných hran}
 209
 210 Nyní ji¾ máme v¹e pøipraveno -- datové struktury, detekci externích vrcholù
 211 a oznaèování ¾ivého podgrafu -- a zbývá doplnit, jak algoritmus kreslí zpìtné
 212 hrany. Jeliko¾ zpìtné hrany vedoucí do~$v$ nemohou zpùsobit slouèení blokù
 213 le¾ících pod~$v$ (na~to jsou potøeba zpìtné hrany vedoucí nìkam nad~$v$ a ty
 214 je¹tì nekreslíme), zpracováváme ka¾dý podstrom zvlá¹». Pøidáme 2-cyklus
 215 pro stromovou hranu, pod nìj pøipojíme blokovou strukturu zatím nakreslené
 216 èásti podstromu a vydáme se po~hranici této struktury nejdøíve jedním
 217 a pak druhým smìrem.
 218
 219 Oba prùchody vypadají následovnì: Procházíme seznam vrcholù na~hranici a neaktivní
 220 vrcholy pøeskakujeme. Pokud objevíme ¾ivý vrchol, nakreslíme v¹e, co z~nìj vede,
 221 pøípadnì se zanoøíme do~¾ivých blokù, které jsou pøipojeny pod tímto vrcholem.
 222 Pokud objevíme externì aktivní vrchol (pøípadnì poté, co jsme ho o¹etøili jako ¾ivý),
 223 procházení zastavíme, proto¾e za externì aktivní vrchol ji¾ nemù¾eme po~této stranì
 224 hranice nic pøipojit, ani¾ by se externì aktivní vrchol dostal dovnitø nakreslení.
 225
 226 Pøitom se øídíme dvìma jednoduchými pravidly:
 227
 228 \s{Pravidlo \#1:} V~ka¾dém ¾ivém vrcholu zpracováváme nejdøíve zpìtné hrany do~$v$,
 229 pak internì aktivní bloky a koneènì externì aktivní bloky pøipojené pod vrcholem.
 230
 231 \s{Pravidlo \#2:} Pokud vstoupíme do~dal¹ího bloku, vybereme si smìr, ve~kterém
 232 budeme pokraèovat (pokud se li¹í od~smìru, ve~kterém zatím hranici
 233 obcházíme, blok pøeklopíme) následovnì: preferujeme smìr k~internì
 234 aktivnímu vrcholu, pokud takový neexistuje, pak k~¾ivému externì aktivnímu
 235 vrcholu.
 236
 237 Èasová slo¾itost této èásti algoritmu je lineární ve~velikosti ¾ivého podgrafu
 238 a¾ na~dvì výjimky. Jednou je konec prohledávání od~posledního ¾ivého vrcholu
 239 k~bodu zastavení, druhou pak vybírání strany hranice pøi vstupu do~bloku.
 240 V~obou mù¾eme procházet a¾ lineárnì mnoho neaktivních vrcholù. Pomù¾eme si
 241 ov¹em snadno: kdykoliv projdeme souvislý úsek hranice tvoøený neaktivními
 242 vrcholy, pøidáme pomocnou hranu, která tento úsek pøeklene. Mù¾eme ji dokonce
 243 pøidat do~nakreslení a podrozdìlit si tak vnìj¹í stìnu.
 244
 245 \h{Hotový algoritmus}
 246
 247 Celý algoritmus tedy bude vypadat takto:
 248
 249 \algo
 250 \:Pokud má graf více ne¾ $3n-6$ vrcholù, odmítneme ho rovnou jako nerovinný.
 251 \:Prohledáme graf $G$ do~hloubky, spoèteme \<Enter,> \<Ancestor> a \<LowPoint> v¹ech vrcholù.
 252 \:Inicializujeme \<SepBlockList> v¹ech vrcholù.
 253 \:Procházíme vrcholy v~poøadí klesajících \<Enter>ù, pro ka¾dý vrchol~$v$:
 254 \::Nakreslíme v¹echny stromové hrany z~$v$ jako 2-cykly.
 255 \::Oznaèíme ¾ivý podgraf.
 256 \::Pro ka¾dého syna vrcholu~$v$ obcházíme ¾ivý podgraf nále¾ící k~tomuto vrcholu
 257    a kreslíme zpìtné hrany do~$v$.
 258 \::Zkontrolujeme, zda v¹echny hrany incidentní s~$v$ byly nakresleny, pokud ne,
 259    prohlásíme graf za~nerovinný a zastavíme se.
 260 \:Projdeme hotové nakreslení do~hloubky a zorientujeme seznamy sousedù.
 261 \endalgo
 262
 263 \s{Vìta:} Tento algoritmus pro ka¾dý graf dobìhne v~èase $\O(n)$ a pokud byl graf rovinný,
 264 vydá jeho nakreslení, v~opaèném pøípadì ohlásí nerovinnost.
 265
 266 \s{Dùkaz:} První krok je korektní, jeliko¾ pro v¹echny rovinné grafy je $m\le 3n-6$; nadále
 267 tedy mù¾eme pøedpokládat, ¾e $m=\O(n)$. Lineární èasovou slo¾itost krokù 4--6 jsme ji¾
 268 diskutovali, kroky~7--8 jsou lineární ve~velikosti ¾ivého podgrafu, a tedy také $\O(n)$.
 269 Nakreslení vydané algoritmem je v¾dy rovinné a v¹echny stromové hrany jsou v¾dy
 270 nakresleny, zbývá tedy ukázat, ¾e zpìtnou hranu mù¾eme nenakreslit jen pokud
 271 graf nebyl rovinný. Tomu vìnujeme zbytek kapitoly.
 272 \qed
 273
 274 \h{Dùkaz korektnosti}
 275
 276 \s{Lemma:} Pokud existuje zpìtná hrana, kterou algoritmus nenakreslil, graf na~vstupu
 277 není rovinný.
 278
 279 \s{Dùkaz:} Rozborem pøípadù uká¾eme, ¾e kdykoliv existuje nenakreslená zpìtná hrana,
 280 pak algoritmus buïto poru¹il Pravidla \#1 a \#2 nebo v~zadaném grafu nalezneme
 281 minor $K_5$ èi $K_{3,3}$.
 282
 283 \todo{Rozebrat hou¹» pøípadù.}
 284
 285 \qed
 286
 287 \s{Poznámka:} Podle tohoto dùkazu bychom také mohli v~lineárním èase v~ka¾dém nerovinném
 288 grafu nalézt Kuratowského podgraf, dokonce také v~$O(n)$, jeliko¾ kdy¾ je $m>3n-6$,
 289 mù¾eme se omezit na~libovolných $3n-5$ hran, které urèitì tvoøí nerovinný podgraf.
 290
 291 \references
 292 \bye