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 \cite{tarjan:planarity}
  12 ukázal, ¾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 preciznì), 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 \todo{Obrázek}
 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.
 122
 123 Jinými slovy $w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud je $\<Ancestor>(w) < \<Enter>(v)$,
 124 nebo pokud pro nìkterého ze~synù $x$ le¾ícího v~jiném bloku je $\<LowPoint>(x) < \<Enter>(x)$.
 125 Ve~statickém grafu by staèilo testovat $\<LowPoint>(w)$, nám se ov¹em bloková
 126 struktura mìní, tak¾e musíme uva¾ovat bloky v~souèasném okam¾iku. Proto si zavademe:
 127
 128 \s{Definice:} $\<SepBlockList>(w)$ je seznam v¹ech synù vrcholu~$w$, které v~daném
 129 okam¾iku le¾í v~jiných blocích ne¾~$w$, setøídìný vzestupnì podle $\<LowPoint>$ù.
 130
 131 \s{Lemma:} Vrchol~$w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud buïto $\<Ancestor>(w) < \<Enter>(v)$,
 132 nebo první prvek $x$ seznamu $\<SepBlockList>(w)$ má $\<LowPoint>(x) < \<Enter>(v)$. Navíc
 133 seznamy \<SepBlockList> je mo¾no udr¾ovat v~amortizovanì konstantním èase.
 134
 135 \s{Dùkaz:} První èást plyne z~definice. V¹echny seznamy na~zaèátku bìhu algoritmu
 136 zkonstruujeme v~lineárním èase pøihrádkovým tøídìním a kdykoliv slouèíme blok
 137 s~koøenem~$x$ s~nadøazeným blokem, odstraníme $x$ ze~seznamu v~pøíslu¹né artikulaci.
 138 \qed
 139
 140 \h{Reprezentace blokù a pøeklápìní}
 141
 142 Pro ka¾dý blok si potøebujeme pamatovat vrcholy, které le¾í na~hranici
 143 (nìkteré z~nich jsou externì aktivní, ale to u¾ umíme poznat) a bloky,
 144 které jsou k~nim pøipojené. Dále je¹tì vnitøní strukturu bloku vèetnì
 145 uvnitø pøipojených dal¹ích blokù, ale jeliko¾ ¾ádné vnitøní vrcholy nejsou
 146 externì aktivní, vnitøek u¾ neovlivní dal¹í výpoèet a potøebujeme jej pouze
 147 pro vypsání výstupu.
 148
 149 Pro na¹e úèely bude staèit zapamatovat si u~ka¾dého bloku, jestli je
 150 oproti nadøazenému bloku pøeklopen. Tuto informaci zapí¹eme do~koøene
 151 bloku. Ka¾dý vrchol na~hranici bloku pak bude obsahovat dva~ukazatele
 152 na~sousední vrcholy. Neumíme sice lokálnì poznat, který ukazatel odpovídá
 153 kterému smìru, ale kdy¾ se nìjakým smìrem vydáme, doká¾eme ho dodr¾et
 154 -- staèí si v¾dy vybrat ten ukazatel, který nás nezavede do~vrcholu,
 155 z~nìj¾ jsme právì pøi¹li.
 156
 157 Ka¾dý vrchol bloku si také bude pamatovat seznam svých sousedù,
 158 podle orientace bloku buïto v~hodinkovém nebo opaèném poøadí.
 159 Chceme-li pøidat hranu, potøebujeme tedy znát abslolutní orientaci,
 160 ale to pùjde snadno, jeliko¾ hrany pøidáváme jen k~vrcholùm na~hranici
 161 a v¾dy k~nim po~hranici dojdeme z~koøene.
 162
 163 K~pøeklopení bloku vèetnì v¹ech podøízených blokù tedy staèí invertovat
 164 bit v~koøeni, pokud chceme pøeklopit jen tento blok, invertujeme bity
 165 i v~koøenech v¹ech podøízených blokù, které najdeme obcházením hranice.
 166
 167 Na~konci algoritmu spustíme post-processing, který v¹echny pøeklápìcí
 168 bity pøenese ve~smìru od~koøene k~potomkùm a urèí tak absolutní orientaci
 169 v¹ech seznamù.
 170
 171 \h{Pøidávání vrcholu}
 172
 173 \todo{Kostra algoritmu. ®ivé vrcholy a jejich nalezení.}
 174
 175 \h{Pøidávání hran}
 176
 177 \todo{Jak se obchází hranice a v~jakém poøadí se co zpracovává.}
 178
 179 \h{Dùkaz korektnosti}
 180
 181 \todo{Èasová slo¾itost se doká¾e snadno, ale na~korektnost je potøeba rozebírat hou¹» pøípadù.}
 182
 183 \todo{Izolace Kuratowského podgrafù.}
 184
 185 \references
 186 \bye