Suffixove stromy: Lepsi vyklad Ukkonenova algoritmu

[ga.git] / 11-planar / 11-planar.tex

\input ../sgr.tex

\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,
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 ukázal \cite{tarjan:planarity},
¾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}, a ten zde uká¾eme.

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í 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{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 stromové a zpìtné hrany. DFS strom
tvoøí kostru grafu.

Nyní u¾ se zamìøíme pouze na~neorientované grafy~\dots

\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); ekvivalenèní tøídy s~jedinou hranou (mosty) pova¾ujeme
za triviální 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¾í 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ù.

Nyní si staèí rozmyslet, jak existenci zpìtných hran testovat rychle. K~tomu se bude hodit:

\s{Definice:} Je-li $v$ vrchol grafu, pak:
\itemize\ibull
\:$\<Enter>(v)$ udává poøadí, v~nìm¾ DFS do~vrcholu~$v$ vstoupilo.
\:$\<Ancestor>(v)$ je nejmen¹í z~\<Enter>ù vrcholù, do~nich¾ vede z~$v$ zpìtná hrana,
nebo $+\infty$, pokud z~$v$ ¾ádná zpìtná hrana nevede.
\:$\<LowPoint>(v)$ je minimum z~\<Ancestor>ù vrcholù le¾ících v~podstromu pod~$v$, vèetnì $v$ samého.
\endlist

\s{Pozorování:} \<Enter>, \<Ancestor> i \<LowPoint> 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:

\s{Lemma:} Pokud $v$ je vrchol grafu, $u$ jeho otec a $w$ jeho syn v~DFS stromu,
pak stromové hrany $uv$ a $vw$ le¾í v~tomté¾ bloku ($uv\sim vw$) právì
tehdy, kdy¾ $\<LowPoint>(w) < \<Enter>(v)$, a~$v$ je artikulace právì kdy¾
nìkterý z~jeho synù $w$ má $\<LowPoint>(w) \ge \<Enter>(v)$.
Koøen DFS stromu je artikulace, právì kdy¾ má více ne¾ jednoho syna.

\h{Postup kreslení}

Graf budeme kreslit v~opaèném poøadí oproti DFS, tj. od~nejvìt¹ích \<Enter>ù 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, s~výjimkou nejvy¹¹ího bloku
je tento koøen souèasnì artikulací v~nadøazeném bloku. Aby se nám tato situace snadno
reprezentovala, artikulace naklonujeme a ka¾dý blok dostane svou vlastní 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 v~libovolném nakreslení mù¾eme kterýkoliv blok spolu se v¹emi bloky
le¾ícími pod~ním pøeklopit podle koøenové artikulace, ani¾ bychom poru¹ili
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í 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í} 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.

Základním krokem algoritmu tedy bude roz¹íøit nakreslení o~nový
vrchol~$v$ a o~v¹echny hrany vedoucí z~nìj do~jeho (ji¾ nakreslených)
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í, 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í 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í 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í 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 externost
nadefinujeme tak, aby pokrývala i tyto pøípady:

\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. Ostatním vrcholùm
budeme øíkat {\I interní.}

Jinými slovy platí, ¾e vrchol $w$ je externí pøi zpracování vrcholu~$v$, pakli¾e $\<Ancestor>(w) < \<Enter>(v)$,
nebo pokud pro nìkterého ze~synù $x$ le¾ícího v~jiném bloku je $\<LowPoint>(x) < \<Enter>(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~\<Ancestor>ù
v¹ech vrcholù le¾ících uvnitø bloku je pøesnì \<LowPoint> tohoto syna.
Ve~statickém grafu by se v¹echny testy redukovaly na~$\<LowPoint>(w)$, nám se ov¹em bloková
struktura prùbì¾nì mìní, tak¾e musíme uva¾ovat bloky v~souèasném okam¾iku. Proto si zavedeme:

\s{Definice:} $\<BlockList>(w)$ je seznam v¹ech blokù pøipojených v~daném okam¾iku
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 $\<LowPoint>$ù synù.

\s{Lemma:} Vrchol~$w$ je externí pøi zpracování vrcholu~$v$, pokud je buïto $\<Ancestor>(w) < \<Enter>(v)$,
nebo první prvek seznamu $\<BlockList>(w)$ má $\<LowPoint> < \<Enter>(v)$. Navíc
seznamy \<BlockList> lze udr¾ovat v~amortizovanì konstantním èase.

\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

\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í, 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í, 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~právì
opu¹tìného vrcholu.

Ka¾dý vrchol 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 absolutní orientaci,
ale to pùjde snadno, jeliko¾ hrany pøidáváme jen k~vrcholùm na~hranici,
poté co k~nim po~hranici dojdeme z~koøene.

K~pøeklopení bloku vèetnì v¹ech podøízených blokù nám 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ù, je¾ najdeme obcházením hranice.

Na~konci algoritmu spustíme dodateèný prùchod, 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ù sousedù i hranic.

\h{®ivý podgraf}

Kdy¾ nakreslíme nový vrchol~$v$ a z~nìj vedoucí stromové hrany, musíme obejít
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 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.

®ivé vrcholy pøitom mohou být i~externí (pokud z~nich vedou zpìtné hrany
jak do vrcholu~$v$, tak do je¹tì nenakreslených vrcholù).
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¾
hrana vede, dále artikulaci, pod~ní¾ je tento blok pøipojen, a dal¹í artikulace
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
znaèku vytvoøili, a znaèky patøící ke~starým koøenùm budeme ignorovat, resp. pøepisovat.}

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í 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+\ell)$, kde $k$ je poèet
kreslených zpìtných hran a $\ell$ poèet hran, které zmizely z~vnìj¹í stìny, èili
amortizovanì konstanta.

\proof
Po~¾ádné hranì neprojdeme více ne¾ jednou. Navíc alespoò polovina z~tìch, po~nich¾
jsme pro¹li, zmizí z~vnìj¹í stìny, tak¾e hledání koøenù blokù trvá $\O(\ell)$.
Pro ka¾dou zpìtnou hranu oznaèíme jeden vrchol jako ¾ivý a pak pokraèujeme hledáním
koøenù, které jsme ji¾ zapoèítali.
\qed

\h{Kreslení zpìtných hran}

Nyní ji¾ máme v¹e pøipraveno -- datové struktury, detekci externích vrcholù
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á¹». 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.

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í vrchol (poté, co jsme ho pøípadnì 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é ¾ivé interní bloky a koneènì podøízené ¾ivé 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~¾ivému 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 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.

\h{Hotový algoritmus}

\s{Algoritmus (kreslení do roviny):}

\algo
\:Pokud má graf více ne¾ $3n-6$ hran, odmítneme ho rovnou jako nerovinný.
\:Prohledáme graf $G$ do~hloubky, spoèteme \<Enter,> \<Ancestor> a \<LowPoint> v¹ech vrcholù.
\:Vytvoøíme \<BlockList> v¹ech vrcholù pøihrádkovým tøídìním.
\:Procházíme vrcholy v~poøadí klesajících \<Enter>ù, pro ka¾dý vrchol~$v$:
\::Nakreslíme v¹echny stromové hrany z~$v$ jako triviální bloky \hfil\break (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 skonèíme.
\:Projdeme hotové nakreslení do~hloubky a zorientujeme seznamy sousedù.
\endalgo

\s{Vìta:} Tento algoritmus pro ka¾dý graf dobìhne v~èase $\O(n)$ a pokud byl graf rovinný,
vydá jeho nakreslení, v~opaèném pøípadì ohlásí nerovinnost.

\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)$.
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.
\qed

\h{Dùkaz korektnosti}

\s{Lemma:} Pokud existuje zpìtná hrana, kterou algoritmus nenakreslil, graf na~vstupu
není rovinný.

\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í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í
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í):

\bigskip
\centerline{\epsfbox{minor1.eps}\qquad\epsfbox{minor2.eps}}
\bigskip

Minor~$M$ pøitom odpovídá situaci, kdy $v$ nele¾í v~bloku~$B$. Tento pøípad
snadno vylouèíme, proto¾e $M$ je isomorfní s~grafem $K_{3,3}$. V~grafu se proto
musí vyskytovat~$N$. Tento minor je ale rovinný, tak¾e musíme ukázat, ¾e vnitøek
bloku brání nakreslení hrany~$vw$ dovnitø. V¾dy pak dojdeme k~nìkterému z~následujících
nerovinných minorù ($N_1$ a¾ $N_3$ jsou isomorfní s~$K_{3,3}$ a $N_4$ s~$K_5$):

\bigskip
\centerline{\epsfbox{minor3.eps}\qquad\epsfbox{minor4.eps}}
\bigskip
\centerline{\epsfbox{minor5.eps}\qquad\epsfbox{minor6.eps}}
\bigskip

\>Uva¾me, jak bude $B$ vypadat po~odebrání vrcholu~$v$ a hran z~nìj vedoucích:

\numlist\nalpha
\:{\I pøestane být 2-souvislý} -- tehdy se zamìøíme na~bloky le¾ící na~cestì~$xy$:

\numlist\nparen
\finalfix{\rightskip=0.5\rightskip}
\:{\I $w$ je artikulace} na této cestì -- BÚNO je taková artikulace v~DFS prohledána po~bloku obsahujícím~$x$,
ale pøed~$y$. Tehdy nám jistì $x$ nezabránilo v~tom, abychom do~$w$ do¹li (mù¾e blokovat
jenom jednu stranu hranice), tak¾e jsme se ve~$w$ museli rozhodnout, ¾e pøednostnì zpracujeme
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í,
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
vstoupili mezi~$x$ a~$y$. Abychom se podle pravidla~\#2 rozhodli pro stranu, z~ní¾ nevede
hrana~$vw$, musela na~druhé stranì být také hrana do~$v$, a~proto se v~grafu vyskytuje minor~$M$.
\endlist

\:{\I zùstane 2-souvislý} a vznikne z~nìj nìjaký blok~$B'$ -- tehdy rozebereme, jaké hrany vedou mezi $v$ a $B'$:

\numlist\nparen
\finalfix{\rightskip=0.5\rightskip}
\:{\I více ne¾ dvì hrany} -- minor~$N_2$.
\:{\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í vrchol, a~to dává minor~$N_4$.
\qeditem

\endlist

\endlist

\s{Poznámka:} Podle tohoto dùkazu bychom také mohli v~lineárním èase v~ka¾dém nerovinném
grafu nalézt Kuratowského podgraf, dokonce také v~$O(n)$, jeliko¾ kdy¾ je $m>3n-6$,
mù¾eme se omezit na~libovolných $3n-5$ hran, které urèitì tvoøí nerovinný podgraf.

\references
\bye