From 37f12ae3981f8f05511d2886b62787d34ddb949e Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 24 Jan 2007 21:30:04 +0100 Subject: [PATCH] Kresleni do roviny: drobne upravy a opravy preklepu. --- 11-planar/11-planar.tex | 40 ++++++++++++++++++++-------------------- 1 file changed, 20 insertions(+), 20 deletions(-) diff --git a/11-planar/11-planar.tex b/11-planar/11-planar.tex index 0467ef2..fba5770 100644 --- a/11-planar/11-planar.tex +++ b/11-planar/11-planar.tex @@ -1,6 +1,6 @@ \input ../sgr.tex -\prednaska{11}{Rovinné grafy}{} +\prednaska{11}{Kreslení grafù do~roviny}{} 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, @@ -13,7 +13,7 @@ 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. -Jakmile u¾ nìjaké rovinné nakreslení máme, lze z~nìj celkem snadno vytváøet +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)$, @@ -51,7 +51,7 @@ neexistuj 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 +ani neexistuje, co¾ se nám v~koøeni DFS stromu mù¾e stát), le¾í tyto hrany 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ù. @@ -59,9 +59,9 @@ Nyn \s{Definice:} Je-li $v$ vrchol grafu, pak: \itemize\ibull -\:$\(v)$ udává poøadí, v~nìm¾ prohledávání do~vrcholu~$v$ vstoupilo. +\:$\(v)$ udává poøadí, v~nìm¾ DFS 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$. +\:$\(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 @@ -110,7 +110,7 @@ slou 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. +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 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é. @@ -142,7 +142,7 @@ Tento seznam udr nebo první prvek seznamu $\(w)$ má $\ < \(v)$. Navíc seznamy \ lze udr¾ovat v~amortizovanì konstantním èase. -\proof První èást plyne z~definice. V¹echny seznamy na~zaèátku bìhu algoritmu +\proof První èást plyne pøímo z~definic. V¹echny seznamy na~zaèátku bìhu algoritmu sestrojíme v~lineárním èase pøihrádkovým tøídìním a kdykoliv slouèíme blok s~nadøazeným blokem, odstraníme ho ze~seznamu v~pøíslu¹né artikulaci. \qed @@ -176,7 +176,7 @@ i v~ko 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ù. +v¹ech seznamù sousedù i hranic. \h{®ivý podgraf} @@ -197,9 +197,9 @@ budeme ho naz 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¾ hrana vede, dále artikulaci, pod~ní¾ je tento blok pøipojen, a dal¹í artikulace -na~cestì do~$v$. Poka¾dé, kdy¾ vstoupíme do~bloku (nìjakým vrcholem na~vnìj¹í stìnì), -tedy potøebujeme nalézt koøen bloku. To udìláme tak, ¾e zaèneme obcházet vnìj¹í -stìnu obìma smìry souèasnì, ne¾ dojdeme v~kterémkoliv smìru do~koøene. Navíc si v¹echny +na~cestì do~$v$. Tedy poka¾dé, kdy¾ vstoupíme do~bloku (nìjakým vrcholem na~vnìj¹í stìnì), +potøebujeme nalézt koøen bloku. To udìláme tak, ¾e zaèneme obcházet vnìj¹í +stìnu obìma smìry souèasnì, a¾ dojdeme v~nìkterém smìru do~koøene. Navíc si v¹echny vrcholy, pøes nì¾ jsme pro¹li, oznaèkujeme a pøiøadíme k~nim rovnou ukazatel na~koøen, tudí¾ po~¾ádné èásti hranice neprojdeme vícekrát.\foot{Znaèky ani nebude potøeba mazat, kdy¾ si u nich poznamenáme, který vrchol byl koøenem v~okam¾iku, kdy jsme @@ -225,7 +225,7 @@ Nyn a oznaèování ¾ivého podgrafu -- a zbývá doplnit, jak algoritmus kreslí zpìtné hrany. Jeliko¾ zpìtné hrany vedoucí do~$v$ nemohou zpùsobit slouèení blokù le¾ících pod~$v$ (na~to jsou potøeba zpìtné hrany vedoucí nìkam nad~$v$ a ty -je¹tì nekreslíme), zpracováváme ka¾dý podstrom zvlá¹». Pøidáme triviální blok +je¹tì nekreslíme), zpracováváme ka¾dý podstrom zvlá¹». V¾dy pøidáme triviální blok pro stromovou hranu, pod nìj pøipojíme blokovou strukturu zatím nakreslené èásti podstromu a vydáme se po~hranici této struktury nejdøíve jedním a pak druhým smìrem. @@ -244,10 +244,10 @@ pak pod (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ì (pokud se li¹í od~smìru, ve~kterém zatím hranici -obcházíme, blok pøeklopíme): preferujeme smìr k~internì +budeme pokraèovat, následovnì: preferujeme smìr k~internì aktivnímu vrcholu, pokud takový neexistuje, pak k~¾ivému externì aktivnímu -vrcholu. +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 @@ -259,19 +259,19 @@ p \h{Hotový algoritmus} -Celý algoritmus tedy bude vypadat takto: +Celý algoritmus bude vypadat takto: \algo -\:Pokud má graf více ne¾ $3n-6$ vrcholù, odmítneme ho rovnou jako nerovinný. +\:Pokud má graf více ne¾ $3n-6$ hran, odmítneme ho rovnou jako nerovinný. \:Prohledáme graf $G$ do~hloubky, spoèteme \ \ a \ v¹ech vrcholù. -\:Inicializujeme \ v¹ech vrcholù. +\:Vytvoøíme \ v¹ech vrcholù pøihrádkovým tøídìním. \:Procházíme vrcholy v~poøadí klesajících \ù, pro ka¾dý vrchol~$v$: \::Nakreslíme v¹echny stromové hrany z~$v$ jako triviální bloky (2-cykly). \::Oznaèíme ¾ivý podgraf. \::Pro ka¾dého syna vrcholu~$v$ obcházíme ¾ivý podgraf nále¾ící k~tomuto vrcholu v~obou smìrech a kreslíme zpìtné hrany do~$v$. \::Zkontrolujeme, zda v¹echny zpìtné hrany vedoucí do~$v$ byly nakresleny, a pokud ne, - prohlásíme graf za~nerovinný a zastavíme se. + prohlásíme graf za~nerovinný a konèíme. \:Projdeme hotové nakreslení do~hloubky a zorientujeme seznamy sousedù. \endalgo @@ -280,7 +280,7 @@ vyd \proof První krok je korektní, jeliko¾ pro v¹echny rovinné grafy je $m\le 3n-6$; nadále tedy mù¾eme pøedpokládat, ¾e $m=\O(n)$. Lineární èasovou slo¾itost krokù 4--6 a~9 jsme ji¾ -diskutovali, kroky~7--8 jsou lineární ve~velikosti ¾ivého podgrafu, a tedy také $\O(n)$. +diskutovali, kroky~7--8 jsou lineární ve~velikosti ¾ivého podgrafu, a~tedy také $\O(n)$. Nakreslení vydané algoritmem je v¾dy rovinné a v¹echny stromové hrany jsou v¾dy nakresleny, zbývá tedy ukázat, ¾e zpìtnou hranu mù¾eme nenakreslit jen pokud graf nebyl rovinný. Tomu vìnujeme zbytek kapitoly. -- 2.39.5