From 4cf07d6d220381de8c7bffba2ad2a8cea7b74c66 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 3 Jan 2012 20:56:41 +0100 Subject: [PATCH] Planarita: Zmena terminologie Interni/externi aktivita byla znacne matouci. Zacal jsem proto interne aktivnim vrcholum rikat jen interni a externe aktivnim jen externi. Z neaktivnich se staly pasivni. Jeste budu upravovat. --- 11-planar/11-planar.tex | 119 +++++++++++++++++++++------------------- 1 file changed, 64 insertions(+), 55 deletions(-) diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index d95bfc9..0d69b7d 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -13,29 +13,35 @@ zastav komplikovaný. Od~té doby se objevilo mnoho zjednodu¹ení, prozatím vrcholících algoritmem Boyera a Myrvoldové \cite{boyer:cutting}, a ten zde uká¾eme. -Takté¾ jakmile u¾ 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¹¹í algoritmus \cite{chrobak:grid} kreslící do~møí¾ky $(2n-4)\times (n-2)$. - -Tak s~chutí do toho \dots +Zmiòme je¹tì, ¾e existují i algoritmy, které vytváøejí rovinná nakreslení s~rùznými +speciálními vlastnostmi. Je to napøíklad Schnyderùv algoritmus~\cite{schnyder:grid} +generující v~lineárním èase nakreslení, v~nìm¾ jsou hrany úseèkami a vrcholy +le¾í v~møí¾ových bodech møí¾ky $(n-2)\times (n-2)$, a~o~nìco jednodu¹¹í algoritmus +Chrobaka a Payneho \cite{chrobak:grid} kreslící do~møí¾ky $(2n-4)\times (n-2)$. +Oba ov¹em pracují tak, ¾e vyjdou z~obyèejného rovinného nakreslení a upravují ho, +aby splòovalo dodateèné podmínky. \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í grafu (orientovaného nebo neorientovaného) do~hloubky rozdìlí $E$ -na~ètyøi druhy hran: {\I stromové} (po~nich¾ DFS pro¹lo a rekurzivnì se zavolalo; tyto hrany -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 právì nachází na~zásobníku, a~v~tomto smìru si je zorientujeme), -{\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{Definice:} Prohledávání orientovaného grafu do~hloubky rozdìlí hrany do~ètyø druhù: +\itemize\ibull +\:{\I stromové} -- po~nich DFS pro¹lo a rekurzivnì se zavolalo; tyto hrany +vytváøejí {\I DFS strom} orientovaný z~koøene; +\:{\I zpìtné} -- vedou do~vrcholu, který le¾í na cestì z~koøene DFS stromu +do právì prohledávaného vrcholu; jinými slovy vedou do vrcholu, který se +právì 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; +\:{\I pøíèné} -- zbývající hrany, které vedou do vrcholu ji¾ zpracovaného vrcholu +v~jiném podstromu. +\endlist -\s{Lemma:} Prohledáváme-li do~hloubky neorientovaný graf, nevzniknou ¾ádné dopøedné ani -pøíèné hrany. V~orientovaném grafu mohou existovat dopøedné -a také pøíèné vedoucí \uv{zprava doleva}, tedy do~døíve nav¹tíveného podstromu. +\s{Pozorování:} +Pokud DFS spustíme na neorientovaný graf a hranu, po~ní¾ jsme u¾ jednou pro¹li, +v~opaèném smìru ignorujeme, existují pouze dopøedné a zpìtné hrany. DFS strom +tvoøí kostru grafu. Nyní u¾ se zamìøíme pouze na~neorientované grafy~\dots @@ -67,7 +73,7 @@ nebo $+\infty$, pokud z~$v$ \:$\(v)$ je minimum z~\ù vrcholù le¾ících v~podstromu pod~$v$, vèetnì $v$ samého. \endlist -\s{Pozorování:} \, \ i \ v¹ech vrcholù lze spoèítat +\s{Pozorování:} \, \ i \ v¹ech vrcholù lze spoèítat bìhem prohledávání, tedy také v~lineárním èase. Rozpoznávání blokù a artikulací mù¾eme shrnout do~následujícího lemmatu: @@ -76,7 +82,7 @@ Rozpozn pak stromové hrany $uv$ a $vw$ le¾í v~tomté¾ bloku ($uv\sim vw$) právì tehdy, kdy¾ $\(w) < \(v)$, a~$v$ je artikulace právì kdy¾ nìkterý z~jeho synù $w$ má $\(w) \ge \(v)$. -Koøen DFS stromu je artikulace právì kdy¾ má více ne¾ jednoho syna. +Koøen DFS stromu je artikulace, právì kdy¾ má více ne¾ jednoho syna. \h{Postup kreslení} @@ -96,12 +102,12 @@ rovinnost. \finalfix{ \smallskip \figure{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize} -\figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externì aktivní vrcholy)}{\epsfxsize} +\figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externí vrcholy)}{\epsfxsize} } V¹imnìme si, ¾e pokud vede z~nìjakého u¾ nakresleného vrcholu je¹tì nenakreslená hrana, lze pokraèovat po~nenakreslených hranách a¾ do~koøene DFS stromu. V¹echny vrcholy, ke~kterým -je¹tì bude potøeba nìco pøipojit (takovým budeme øíkat {\I externì aktivní} a hranám +je¹tì bude potøeba nìco pøipojit (takovým budeme øíkat {\I externí} a hranám rovnì¾; za~chvíli to nadefinujeme formálnì), proto 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. @@ -110,35 +116,35 @@ vrchol~$v$ a o~v DFS-následníkù. Stromové hrany pùjdou nakreslit v¾dy, pøidáme je jako triviální bloky (2-cykly) a nejsou-li to mosty, brzy se nìjakou zpìtnou hranou spojí s~jinými bloky. Zpìtné hrany byly a¾ donedávna -externì aktivní, tak¾e pøidání jedné zpìtné hrany nahradí cestu +externí, 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, jak je vidìt z~obrázkù. \separatefix{ \figure{planar1.eps}{Pøed nakreslením zpìtných hran \dots}{\epsfxsize} -\figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externì aktivní vrcholy)}{\epsfxsize} +\figure{planar2.eps}{\dots\ po nìm (ètvereèky jsou externí vrcholy)}{\epsfxsize} } 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 také stát, ¾e zpìtná hrana zakryje nìjaký externì aktivní vrchol. -Tehdy musíme nìkteré bloky pøeklopit tak, aby externì aktivní vrcholy +Mù¾e se nám ale také stát, ¾e zpìtná hrana zakryje nìjaký externí vrchol. +Tehdy musíme nìkteré bloky pøeklopit tak, aby externí 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 poznávat, kdy je pøeklápìní potøebné. -\h{Externí aktivita} +\h{Externí vrcholy} Jestli¾e 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ì -i~vrchol, pøes který je~$B$ pøipojen ke~zbytku grafu. Proto externí aktivitu +i~vrchol, pøes který je~$B$ pøipojen ke~zbytku grafu. Proto externost 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 pod~$w$ pøipojen externì aktivní -blok, èili blok obsahující alespoò jeden externì aktivní vrchol. +\s{Definice:} Vrchol~$w$ je {\I externí,} pokud buïto z~$w$ vede zpìtná +hrana do~je¹tì nenakresleného vrcholu, nebo je pod~$w$ pøipojen externí +blok, èili blok obsahující alespoò jeden externí vrchol. -Jinými slovy vrchol $w$ je externì aktivní pøi zpracování vrcholu~$v$, pakli¾e $\(w) < \(v)$, +Jinými slovy platí, ¾e vrchol $w$ je externí pøi zpracování vrcholu~$v$, pakli¾e $\(w) < \(v)$, nebo pokud pro nìkterého ze~synù $x$ le¾ícího v~jiném bloku je $\(x) < \(v)$. Druhá podmínka funguje díky tomu, ¾e koøen bloku má v~tomto bloku právì jednoho syna (jinak by existovala pøíèná hrana, co¾ víme, ¾e není pravda), tak¾e minimum z~\ù @@ -150,7 +156,7 @@ struktura pr pod vrcholem~$w$, reprezentovaných jejich koøeny (klony vrcholu~$w$) a jedinými syny koøenù. Tento seznam udr¾ujeme setøídìný vzestupnì podle $\$ù synù. -\s{Lemma:} Vrchol~$w$ je externì aktivní pøi zpracování vrcholu~$v$, pokud je buïto $\(w) < \(v)$, +\s{Lemma:} Vrchol~$w$ je externí pøi zpracování vrcholu~$v$, pokud je buïto $\(w) < \(v)$, nebo první prvek seznamu $\(w)$ má $\ < \(v)$. Navíc seznamy \ lze udr¾ovat v~amortizovanì konstantním èase. @@ -162,10 +168,10 @@ s~nad \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, +(nìkteré z~nich jsou externí, ale to u¾ umíme poznat) a bloky, které jsou pod nimi 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 +externí, 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 @@ -196,16 +202,19 @@ Kdy ka¾dý podstrom, ve~vhodném poøadí nakreslit zpìtné hrany do~$v$ a podle potøeby pøeklopit bloky. V~podstromu ov¹em mù¾e být mnoho blokù, které ¾ádnou pozornost nevy¾adují a bìh algoritmu by zbyteènì brzdily. -Proto podobnì jako externí aktivitu nadefinujeme je¹tì -¾ivost vrcholu a ta bude odpovídat zpìtným hranám vedoucím do~$v$. +Proto si pøed samotným kreslením oznaèíme {\I ¾ivou} èást grafu -- to je +èást, kterou potøebujeme bìhem kreslení nav¹tívit; zbytku grafu se budeme +sna¾it vyhýbat, aby nás nezdr¾oval. \s{Definice:} Vrchol~$w$ je {\I ¾ivý,} pokud z~nìj buïto vede zpìtná hrana do~právì zpracovávaného vrcholu~$v$, nebo pokud pod ním je pøipojen ¾ivý blok, -tj. blok obsahující ¾ivý vrchol. Není-li ¾ivý vrchol èi blok externì aktivní, -budeme mu øíkat {\I internì aktivní.} Pakli¾e není vrchol/blok ani ¾ivý, ani externì aktivní, -budeme ho nazývat {\I neaktivní.} -\finalfix{\looseness=1} +tj. blok obsahující ¾ivý vrchol. + +®ivé vrcholy pøitom mohou být i~externí (pokud z~nich vedou zpìtné hrany +jako do vrcholu~$v$, tak do je¹tì nenakreslených vrcholù). Pokud ¾ivý vrchol +není externí, budeme mu øíkat {\I interní.} A~pokud nìjaký vrchol není ani +¾ivý, ani externí, budeme ho nazývat {\I pasivní.} Pøed procházením podstromù tedy nejprve probereme v¹echny zpìtné hrany vedoucí do~$v$ a oznaèíme ¾ivé vrcholy. Pro ka¾dou zpìtnou hranu potøebujeme o¾ivit vrchol, z~nìj¾ @@ -220,12 +229,12 @@ zna Výstupem této èásti algoritmu budou znaèky u~¾ivých vrcholù a u~artikulací také seznamy podøízených ¾ivých blokù. Tyto seznamy budeme udr¾ovat uspoøádané -tak, aby externì aktivní bloky následovaly po~v¹ech internì aktivních. To nám +tak, aby externí bloky následovaly po~v¹ech interních. To nám usnadní práci v~hlavní èásti algoritmu. \s{Lemma:} Pro ka¾dý koøen trvá znaèení ¾ivých vrcholù èas $\O(k+l)$, kde $k$ je poèet kreslených zpìtných hran a $l$ poèet vrcholù, které zmizely z~vnìj¹í stìny, èili -amortizovaná konstanta. +amortizovanì konstanta. \proof Alespoò polovina vrcholù, po~nich¾ jsme v~libovolném bloku pro¹li, zmizí z~vnìj¹í stìny, tak¾e hledání koøenù blokù trvá $\O(l)$. Pro ka¾dou zpìtnou @@ -243,30 +252,30 @@ pro stromovou hranu, pod n èásti podstromu a vydáme se po~hranici této struktury nejdøíve jedním a pak druhým smìrem. -Oba prùchody vypadají následovnì: Procházíme seznam vrcholù na~hranici a neaktivní +Oba prùchody vypadají následovnì: Procházíme seznam vrcholù na~hranici a pasivní vrcholy pøeskakujeme. Pokud objevíme ¾ivý vrchol, nakreslíme v¹e, co z~nìj vede, pøípadnì se zanoøíme do~¾ivých blokù, které jsou pøipojeny pod tímto vrcholem. -Pokud objevíme externì aktivní vrchol (pøípadnì poté, co jsme ho o¹etøili jako ¾ivý), -procházení zastavíme, proto¾e za externì aktivní vrchol ji¾ nemù¾eme po~této stranì -hranice nic pøipojit, ani¾ by se externì aktivní vrchol dostal dovnitø nakreslení. +Pokud objevíme externí vrchol (pøípadnì poté, co jsme ho o¹etøili jako ¾ivý), +procházení zastavíme, proto¾e za externí vrchol ji¾ nemù¾eme po~této stranì +hranice nic pøipojit, ani¾ by se externí vrchol dostal dovnitø nakreslení. Pøitom se øídíme dvìma jednoduchými pravidly: \s{Pravidlo \#1:} V~ka¾dém ¾ivém vrcholu zpracováváme nejdøíve zpìtné hrany do~$v$, -pak podøízené internì aktivní bloky a koneènì podøízené externì aktivní bloky. +pak podøízené interní bloky a koneènì podøízené externí bloky. (K~tomu se nám hodí, ¾e máme seznamy ¾ivých podøízených blokù setøídìné.) \s{Pravidlo \#2:} Pokud vstoupíme do~dal¹ího bloku, vybereme si smìr, ve~kterém -budeme pokraèovat, následovnì: preferujeme smìr k~internì -aktivnímu vrcholu, pokud takový neexistuje, pak k~¾ivému externì aktivnímu +budeme pokraèovat, následovnì: preferujeme smìr k~internímu +vrcholu, pokud takový neexistuje, pak k~¾ivému externímu vrcholu. Pokud se tento smìr li¹í od~smìru, ve~kterém jsme zatím hranici obcházeli, blok pøeklopíme. Èasová slo¾itost této èásti algoritmu je lineární ve~velikosti ¾ivého podgrafu a¾ na~dvì výjimky. Jednou je konec prohledávání od~posledního ¾ivého vrcholu k~bodu zastavení, druhou pak vybírání strany hranice pøi vstupu do~bloku. -V~obou mù¾eme procházet a¾ lineárnì mnoho neaktivních vrcholù. Pomù¾eme si -ov¹em snadno: kdykoliv projdeme souvislý úsek hranice tvoøený neaktivními +V~obou mù¾eme procházet a¾ lineárnì mnoho pasivních vrcholù. Pomù¾eme si +ov¹em snadno: kdykoliv projdeme souvislý úsek hranice tvoøený pasivními vrcholy, pøidáme pomocnou hranu, která tento úsek pøeklene. Mù¾eme ji dokonce pøidat do~nakreslení a podrozdìlit si tak vnìj¹í stìnu. @@ -306,15 +315,15 @@ nen \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ì aktivními vrcholy. Rozborem pøípadù uká¾eme, +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. -Oznaème $B$ blok, ve~kterém le¾í na~obou stranách hranice nìjaké externì aktivní +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ì aktivní): +vybarvená èást odpovídá vnitøku bloku; hranaté vrcholy jsou externí): \bigskip \centerline{\epsfbox{minor1.eps}\qquad\epsfbox{minor2.eps}} @@ -345,7 +354,7 @@ jenom jednu stranu hranice), tak 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ì aktivní, +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 @@ -361,7 +370,7 @@ hrana~$vw$, musela na~druh \:{\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ì aktivní vrchol, a~to dává minor~$N_4$. +je-li na~spodní cestì je¹tì jeden externí vrchol, a~to dává minor~$N_4$. \qeditem \endlist -- 2.39.2