From b959c38583c5f82ef4040444f2800f7726ebedf2 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 15 Jan 2007 01:15:36 +0100 Subject: [PATCH] Prvni cast planarity. --- 11-planar/11-planar.tex | 186 ++++++++++++++++++++++++++++++++++++++++ 11-planar/Makefile | 3 + all/Makefile | 2 +- ga.bib | 41 +++++++++ 4 files changed, 231 insertions(+), 1 deletion(-) create mode 100644 11-planar/11-planar.tex create mode 100644 11-planar/Makefile diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex new file mode 100644 index 0000000..dc9c7ff --- /dev/null +++ b/11-planar/11-planar.tex @@ -0,0 +1,186 @@ +\input ../sgr.tex + +\prednaska{11}{Rovinné grafy}{} + +Rovinné grafy se objevují v~nejrùznìj¹ích praktických aplikacích teorie grafù, +a~tak okolo nich vyrostlo znaèné mno¾ství algoritmù. I~kdy¾ existují výjimky, +jako napøíklad ji¾ zmínìné hledání kostry rovinného grafu, vìt¹ina takových +algoritmù pracuje s~konkrétním vnoøením grafu do~roviny (rovinným nakreslením). + +Proto se zamìøíme na~algoritmus, který zadaný graf buïto vnoøí do~roviny, nebo se +zastaví s~tím, ¾e graf není rovinný. Tarjan ji¾ v~roce 1974 \cite{tarjan:planarity} +ukázal, ¾e je to mo¾né provést v~lineárním èase, ale jeho algoritmus je ponìkud +komplikovaný. Od~té doby se objevilo mnoho zjednodu¹ení, prozatím vrcholících +algoritmem Boyera a Myrvoldové \cite{boyer:cutting}, který zde uká¾eme. + +Jakmile nìjaké rovinné nakreslení máme, lze z~nìj celkem snadno vytváøet +rovinná nakreslení s~rùznými speciálními vlastnostmi. Za~zmínku stojí napøíklad +Schnyderùv algoritmus \cite{schnyder:grid} generující v~lineárním èase nakreslení, +v~nìm¾ v¹echny hrany jsou úseèky a vrcholy le¾í v~møí¾ových bodech møí¾ky $(n-2)\times (n-2)$, +a~o~nìco jednodu¹¹í varianta \cite{chrobak:grid} do~møí¾ky $(2n-4)\times (n-2)$. + +\h{DFS a bloky} + +Pøipomeòme si nejprve nìkteré vlastnosti prohledávání do~hloubky (DFS) a jeho pou¾ití +k~hledání komponent vrcholové 2-souvislosti {\I (blokù).} + +\s{Definice:} Prohledávání do~hloubky rozdìlí $E$ na~ètyøi druhy hran: {\I stromové} (po~nich¾ +DFS pro¹lo a rekurzivnì se zavolalo; vytváøejí {\I DFS strom} orientovaný z~koøene), +{\I zpìtné} (vedou do~vrcholu na~cestì mezi prohledávaným vrcholem a koøenem, +èili do~takového, který se nachází na~zásobníku), {\I dopøedné} vedou do~ji¾ zpracovaného +vrcholu le¾ícího v~DFS stromu pod aktuálním vrcholem a zbývající {\I pøíèné} (z~tohoto vrcholu +do~jiného podstromu). + +\s{Lemma:} Prohledáváme-li do~hloubky neorientovaný graf, nevzniknou ¾ádné dopøedné ani +pøíèné hrany.\foot{Pro úplnost: v~orientovaném grafu mohou existovat dopøedné +a také pøíèné vedoucí \uv{zprava doleva}, tedy døíve nav¹tívené komponenty.} + +\s{Lemma:} Relace \uv{Hrany $e$ a $f$ le¾í na~spoleèné kru¾nici} (znaèíme $e\sim f$) je ekvivalence. Její +tøídy tvoøí maximální 2-souvislé podgrafy (bloky). Vrchol $v$ je artikulace právì tehdy, +sousedí-li s~ním hrany z~více blokù. + +Pokud spustíme na~graf DFS, je pøirozené testovat, do~jakých blokù patøí stromové +hrany sousedící s~právì prohledávaným vrcholem~$v$: stromová hrana $uv$, po~které jsme +do~$v$ pøi¹li, a hrany $vw_1$ a¾ $vw_k$ vedoucí do~podstromù $T_1$ a¾ $T_k$ (zpìtné hrany +jsou v¾dy ekvivalentní s~hranou $uv$). Pokud je $uv \sim vw_i$, musí existovat cesta +z~podstromu $T_i$ do~vrcholu~$u$, která nepou¾ije právì testované hrany. Taková cesta +ale mù¾e podstrom opustit pouze zpìtnou hranou (stromová je zakázaná a dopøedné ani pøíèné +neexistují). Jinými slovy $uv\sim vw_i$ právì tehdy, kdy¾ existuje zpìtná hrana z~podstromu~$T_i$ +do~vrcholu $u$ nebo blí¾e ke~koøeni. + +Pokud nìkterá dvojice $vw_i$, $vw_j$ není ekvivalentní pøes hranu $uv$ (nebo pokud hrana $uv$ +ani neexistuje, co¾ se nám v~koøeni DFS stromu mù¾e stát), le¾í v~rùzných blocích, proto¾e +$T_i$ a $T_j$ mohou být spojeny jen pøes své koøeny (pøíèné hrany neexistují). Ze~zpìtných +hran tedy získáme kompletní strukturu blokù. + +Nyní si staèí rozmyslet, jak zpìtné hrany testovat efektivnì. K~tomu si zavedeme: + +\s{Definice:} Pro vrchol $v$ zavedeme: +\itemize\ibull +\:$\(v)$ udává poøadí, v~nìm¾ prohledávání do~vrcholu~$v$ vstoupilo. +\:$\(v)$ je nejmen¹í z~\ù vrcholù, do~nich¾ vede z~$v$ zpìtná hrana. +\:$\(v)$ je minimum z~\ù vrcholù le¾ících v~podstromu pod~$v$. +\endlist + +\s{Pozorování:} \, \ i \ v¹ech vrcholù lze spoèítat +bìhem prohledávání, tedy také v~lineárním èase. + +\s{Lemma:} +Stromové hrany $uv$ a $vw$ le¾í v~tomté¾ bloku (tedy $uv\sim vw$) právì +tehdy, kdy¾ $\(w) < \(v)$. Vrchol~$v$ je artikulace právì +tehdy, kdy¾ nìkterý z~jeho synù $w$ má $\(w) \ge \(v)$. + +\h{Postup kreslení} + +Graf budeme kreslit v~opaèném DFS-poøadí, tj. od~nejvìt¹ích \ù k~nejmen¹ím, +a v¾dy si budeme udr¾ovat blokovou strukturu ji¾ nakreslené èásti grafu uspoøádanou +podle DFS stromu -- ka¾dý blok bude mít svùj koøen a (mimo nejvy¹¹ího bloku) +bude zavì¹en pod artikulací le¾ící v~nadøazeném bloku. Aby se nám tato +situace snadno reprezentovala, mù¾eme artikulace naklonovat a ka¾dý blok +pak dostane jednu kopii artikulace. + +Také budeme vyu¾ívat toho, ¾e nakreslení ka¾dého bloku, který není +most, je ohranièeno kru¾nicí, a mosty zdvojíme, aby to pro nì platilo +také. Navíc libovolný blok spolu se v¹emi bloky le¾ícími pod~ním +mù¾eme v~rovinì pøeklopit. + +V¹imnìme si, ¾e pokud vede z~nìjakého u¾ nakresleného vrcholu~$v$ je¹tì nenakreslená hrana, +lze pokraèovat po~nenakreslených hranách a¾ do~koøene. V¹echny vrcholy, ke~kterým +je¹tì bude potøeba nìco pøipojit (takovým budeme øíkat {\I externì aktivní} a za~chvíli +to nadefinujeme preciznì), tedy musí le¾et v~té¾e stìnì dosud nakresleného +podgrafu a bez újmy na~obecnosti si vybereme, ¾e to bude vnìj¹í stìna. + +Základním krokem algoritmu tedy bude roz¹íøit nakreslení o~nový vrchol~$v$, +je-li v¹e v~DFS poøadí následující po~tomto vrcholu ji¾ nakresleno, +a o~v¹echny s~ním incidentní hrany. Stromové hrany pùjdou nakreslit v¾dy, +pøidáme je jako 2-cykly a a¾ se uká¾e, ¾e to nejsou mosty, pøipojíme +je k~pøíslu¹nému bloku. Zpìtné hrany byly a¾ do~nedávna externì aktivní, +tak¾e pøidání jedné zpìtné hrany nahradí cestu po~okraji bloku +touto hranou (tím vytvoøí novou stìnu) a také mù¾e slouèit nìkolik +blokù do~jednoho: + +\todo{Obrázek} + +Bude se nám hodit, ¾e èas potøebný na~tuto operaci je pøímo úmìrný poètu +hran, které ubyly z~vnìj¹í stìny, co¾ je amortizovanì konstanta. + +Mù¾e se nám ale stát, ¾e zpìtná hrana zakryje nìjaký externì aktivní vrchol. +Tehdy potøebujeme nìkteré bloky pøeklopit tak, aby externì aktivní vrcholy +zùstaly venku. Potøebujeme tedy datové struktury, pomocí nich¾ bude mo¾né +pøeklápìt efektivnì a co víc, také rychle poznat, kdy je pøeklápìní potøebné. + +\h{Externí aktivita} + +Pokud z~nìjakého vrcholu~$v$ bloku~$B$ vede dosud nenakreslená hrana, musí +být tento vrchol na~vnìj¹í stìnì, tak¾e musí také zùstat na~vnìj¹í stìnì +vrchol, pøes který je~$B$ pøipojen ke~zbytku grafu. Proto externí aktivitu +nadefinujeme tak, aby pokrývala i tyto pøípady: + +\s{Definice:} Vrchol~$w$ je {\I externì aktivní} pokud buïto z~$w$ vede zpìtná +hrana do~je¹tì nenakresleného vrcholu, nebo je k~$w$ pøipojen externì aktivní +blok, èili blok obsahující alespoò jeden externì aktivní vrchol. + +Jinými slovy $w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud je $\(w) < \(v)$, +nebo pokud pro nìkterého ze~synù $x$ le¾ícího v~jiném bloku je $\(x) < \(x)$. +Ve~statickém grafu by staèilo testovat $\(w)$, nám se ov¹em bloková +struktura mìní, tak¾e musíme uva¾ovat bloky v~souèasném okam¾iku. Proto si zavademe: + +\s{Definice:} $\(w)$ je seznam v¹ech synù vrcholu~$w$, které v~daném +okam¾iku le¾í v~jiných blocích ne¾~$w$, setøídìný vzestupnì podle $\$ù. + +\s{Lemma:} Vrchol~$w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud buïto $\(w) < \(v)$, +nebo první prvek $x$ seznamu $\(w)$ má $\(x) < \(v)$. Navíc +seznamy \ je mo¾no udr¾ovat v~amortizovanì konstantním èase. + +\s{Dùkaz:} První èást plyne z~definice. V¹echny seznamy na~zaèátku bìhu algoritmu +zkonstruujeme v~lineárním èase pøihrádkovým tøídìním a kdykoliv slouèíme blok +s~koøenem~$x$ s~nadøazeným blokem, odstraníme $x$ ze~seznamu v~pøíslu¹né artikulaci. +\qed + +\h{Reprezentace blokù a pøeklápìní} + +Pro ka¾dý blok si potøebujeme pamatovat vrcholy, které le¾í na~hranici +(nìkteré z~nich jsou externì aktivní, ale to u¾ umíme poznat) a bloky, +které jsou k~nim pøipojené. Dále je¹tì vnitøní strukturu bloku vèetnì +uvnitø pøipojených dal¹ích blokù, ale jeliko¾ ¾ádné vnitøní vrcholy nejsou +externì aktivní, vnitøek u¾ neovlivní dal¹í výpoèet a potøebujeme jej pouze +pro vypsání výstupu. + +Pro na¹e úèely bude staèit zapamatovat si u~ka¾dého bloku, jestli je +oproti nadøazenému bloku pøeklopen. Tuto informaci zapí¹eme do~koøene +bloku. Ka¾dý vrchol na~hranici bloku pak bude obsahovat dva~ukazatele +na~sousední vrcholy. Neumíme sice lokálnì poznat, který ukazatel odpovídá +kterému smìru, ale kdy¾ se nìjakým smìrem vydáme, doká¾eme ho dodr¾et +-- staèí si v¾dy vybrat ten ukazatel, který nás nezavede do~vrcholu, +z~nìj¾ jsme právì pøi¹li. + +Ka¾dý vrchol bloku si také bude pamatovat seznam svých sousedù, +podle orientace bloku buïto v~hodinkovém nebo opaèném poøadí. +Chceme-li pøidat hranu, potøebujeme tedy znát abslolutní orientaci, +ale to pùjde snadno, jeliko¾ hrany pøidáváme jen k~vrcholùm na~hranici +a v¾dy k~nim po~hranici dojdeme z~koøene. + +K~pøeklopení bloku vèetnì v¹ech podøízených blokù tedy staèí invertovat +bit v~koøeni, pokud chceme pøeklopit jen tento blok, invertujeme bity +i v~koøenech v¹ech podøízených blokù, které najdeme obcházením hranice. + +Na~konci algoritmu spustíme post-processing, který v¹echny pøeklápìcí +bity pøenese ve~smìru od~koøene k~potomkùm a urèí tak absolutní orientaci +v¹ech seznamù. + +\h{Pøidávání vrcholu} + +\todo{Kostra algoritmu. ®ivé vrcholy a jejich nalezení.} + +\h{Pøidávání hran} + +\todo{Jak se obchází hranice a v~jakém poøadí se co zpracovává.} + +\h{Dùkaz korektnosti} + +\todo{Èasová slo¾itost se doká¾e snadno, ale na~korektnost je potøeba rozebírat hou¹» pøípadù.} + +\todo{Izolace Kuratowského podgrafù.} + +\references +\bye diff --git a/11-planar/Makefile b/11-planar/Makefile new file mode 100644 index 0000000..124e770 --- /dev/null +++ b/11-planar/Makefile @@ -0,0 +1,3 @@ +P=11-planar + +include ../Makerules diff --git a/all/Makefile b/all/Makefile index 2d70065..8cee570 100644 --- a/all/Makefile +++ b/all/Makefile @@ -1,5 +1,5 @@ P=ga -X=$(shell for a in 0 1 2 3 4 5 6 7 8 9 10 ; do echo ../$$a-*/$$a-*.tex ; done) +X=$(shell for a in 0 1 2 3 4 5 6 7 8 9 10 11 ; do echo ../$$a-*/$$a-*.tex ; done) include ../Makerules diff --git a/ga.bib b/ga.bib index 43c7e23..ffd73c4 100644 --- a/ga.bib +++ b/ga.bib @@ -330,3 +330,44 @@ publisher = "SNTL", address = "Praha" } + +@article{ boyer:cutting, + title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}}, + author={Boyer, J.M. and Myrvold, W.J.}, + journal={Journal of Graph Algorithms and Applications}, + volume={8}, + number={3}, + pages={241--273}, + year={2004} +} + +@article{ tarjan:planarity, + title={{Efficient Planarity Testing}}, + author={Hopcroft, J. and Tarjan, R.}, + journal={Journal of the ACM (JACM)}, + volume={21}, + number={4}, + pages={549--568}, + year={1974}, + publisher={ACM Press New York, NY, USA} +} + +@article{ schnyder:grid, + title={{Embedding planar graphs on the grid}}, + author={Schnyder, W.}, + journal={Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms}, + pages={138--148}, + year={1990}, + publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA} +} + +@article{ chrobak:grid, + title={{A linear-time algorithm for drawing a planar graph on a grid}}, + author={Chrobak, M. and Payne, T. H.}, + journal={Information Processing Letters}, + volume={54}, + number={4}, + pages={241--246}, + year={1995}, + publisher={Elsevier Science} +} -- 2.39.2