From e08a9ead8ad6e399ae24fce44d44065014a8ce7a Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 15 Jun 2009 22:16:04 +0200 Subject: [PATCH] Opravena verze kapitoly o DFS. --- 3-dfs/3-dfs.tex | 110 ++++++----- 3-dfs/imgn_nei.eps | 457 +++++++++++++++++++++++++++++++++++++++++++++ 3-dfs/imgn_o4.eps | 253 +++++++++++++++++++++++++ 3 files changed, 775 insertions(+), 45 deletions(-) create mode 100644 3-dfs/imgn_nei.eps create mode 100644 3-dfs/imgn_o4.eps diff --git a/3-dfs/3-dfs.tex b/3-dfs/3-dfs.tex index 7fce756..b183ac4 100644 --- a/3-dfs/3-dfs.tex +++ b/3-dfs/3-dfs.tex @@ -2,16 +2,19 @@ \prednaska{3}{Prohledání do~¹íøky a do~hloubky}{()} -\h{Prohledání do~¹íøky (BFS) {\I Breadth First Search} } +\h{Prohledání do~¹íøky (BFS) {\I Breadth-First Search} } Jde o grafový algoritmus, který postupnì prochází v¹echny vrcholy v~dané komponentì souvislosti. -Algoritmus nejprve projde v¹echny sousedy poèáteèního vrcholu, poté sousedy sousedù, atd... +Algoritmus nejprve projde v¹echny sousedy poèáteèního vrcholu, poté sousedy sousedù, atd\dots Díky tomuto zpùsobu procházení se nìkdy té¾ nazývá \uv{\I algoritmus vlny }, nebo» se z~poèáteèního vrcholu ¹íøí pomyslná vlna, která v~ka¾dém kroku nalezne v¹echny uzly, které mají od~poèáteèního vrcholu stejnou vzdálenost. Algoritmus se tedy skvìle hodí napøíklad pro hledání nejkra¹í cesty mezi dvìma vrcholy v~grafu. \figure{praseci-graf.eps}{Praseèí graf}{55mm} \s{Popis algoritmu:} -Na zaèátku si vlo¾íme do~fronty $Q$ poèáteèní vrchol $v_0$. Dále si v~poli $Z$ budeme pro ka¾dý vrchol pamatovat znaèku, zda jsme ho ji¾ nav¹tívili, èi nikoli. Pro vrchol $v_0$ si tedy dosazením jednièky zapamatujeme, ¾e je ji¾ nav¹tívený. V~dal¹ím kroku pak zkoumáme frontu $Q$: pokud není prázdná, vezmeme z~ní první vrchol a podíváme se na~v¹echny jeho sousedy $w$. Pokud je¹tì nejsou oznaèené (tedy $Z[w]=0$), tak je oznaèíme (zapamatujeme si, ¾e je pøedáváme ke zpracování a u¾ je nemáme znovu nav¹tìvovat) a pøidáme je do~fronty k~následnému zpracování. Takto cyklus opakujeme, dokud není fronta prázdná. +Na zaèátku vlo¾íme do~fronty $Q$ poèáteèní vrchol $v_0$. Dále si v~poli $Z$ budeme pro ka¾dý vrchol pamatovat znaèku, zda jsme ho ji¾ nav¹tívili, èi nikoli. Pro vrchol $v_0$ si tedy dosazením jednièky zapamatujeme, ¾e je ji¾ nav¹tívený. V~dal¹ím kroku pak zkoumáme frontu $Q$: pokud není prázdná, vezmeme z~ní první vrchol a podíváme se na~v¹echny jeho sousedy $w$. Pokud je¹tì nejsou oznaèené (tedy $Z[w]=0$), tak je oznaèíme (zapamatujeme si, ¾e je pøedáváme ke zpracování a u¾ je nemáme znovu nav¹tìvovat) a pøidáme je do~fronty k~následnému zpracování. Takto cyklus opakujeme, dokud není fronta prázdná. + +\s{Poznámka:} +Nejprve se podívejme, jak algoritmus pracuje na orientovaném grafu. Pro neorientovaný graf funguje algoritmus analogicky, co¾ si uká¾eme pozdìji. \s{Algoritmus:} @@ -20,7 +23,7 @@ Na za \:$Z[*] \leftarrow 0, Z[v_0] \leftarrow 1$. \:Dokud $Q \not= \emptyset $ opakujeme: \::Vyzvedneme vrcholy $u$ z~$Q$. -\::$\forall w: \{u,w\} \in E$: +\::$\forall w: (u,w)\in E$: \:::Je-li $Z[w]=0 \Rightarrow Z[w] \leftarrow 1$, pøidáme $w$ do~$Q$. \endalgo @@ -35,9 +38,9 @@ Na za \uv{$\Longrightarrow$}: Platí jako invariant po celou dobu bìhu algoritmu. To doká¾eme indukcí dle doby bìhu algoritmu: -První krok indukce je triviální, nebo» cesta z~$v_0$ do~$v_0$ existuje v¾dy. Nyní si pøedstavme, ¾e oznaèujeme vrchol $v$ pøes hranu $uv$. To znamená, ¾e vrchol $u$ ji¾ musel být oznaèený. Dle indukèního pøedpokladu tedy existuje cesta z~$v_0$ do~$u$, a tudí¾ pokud k~této cestì \uv{pøilepíme} hranu $uv$, tak máme hledanou cestu z~$v_0$ do~$v$. +První krok indukce je triviální, nebo» cesta z~$v_0$ do~$v_0$ existuje v¾dy. Nyní si pøedstavme, ¾e oznaèujeme vrchol~$v$ pøes hranu~$uv$. To znamená, ¾e vrchol~$u$ ji¾ musel být oznaèený. Dle indukèního pøedpokladu tedy existuje cesta z~$v_0$ do~$u$, a tudí¾ pokud k~této cestì \uv{pøilepíme} hranu~$uv$, dostáváme sled z~$v_0$ do~$v$, který lze v¾dy zredukovat na cestu. -\uv{$\Longleftarrow$} Sporem: Nech» existuje neoznaèený vrchol $v$ dosa¾itelný po nìjaké cestì z~$v_0$. Uva¾me nejkrat¹í cestu $(v_0, v)$: $v_0, \dots, u, v$. Pøedposlední vrchol na~této cestì (vrchol $u$) musí být oznaèený. Vrchol $u$ se dostane do~fronty, pak je z~ní vybrán a tím se zpracuje i vrchol $v$, co¾ je SPOR. \qed +\uv{$\Longleftarrow$} Sporem: Nech» existuje neoznaèený vrchol $v$ dosa¾itelný po nìjaké cestì z~$v_0$. Uva¾me nejkrat¹í cestu $(v_0, v)$: $v_0, v_1 \dots, v_k = v$ a vezmìme minimální~$i$ takové, ¾e~$v_i$ není oznaèený. Víme, ¾e~$i>0$ (nebo»~$v_0$ je urèitì oznaèen u¾ na zaèátku algoritmu). Tudí¾~$v_{i-1}$ je oznaèený. Museli jsme tedy pou¾ít hranu~$v_{i-1}~v_i$ a oznaèit vrchol~$v_i$, co¾ je SPOR. \qed Nyní tedy víme, ¾e je algoritmus správný, a máme pøedstavu o tom, jak funguje. Podíváme-li se na~nìj podrobnìji, zjistíme, ¾e je hodnì závislý na~tom, jak si budeme graf pamatovat. Zanedlouho zároveò zjistíme, ¾e nám reprezentace grafu v~pamìti znatelnì ovlivní èasovou (i pamì»ovou) slo¾itost celého algoritmu. @@ -46,8 +49,7 @@ Nyn Oznaème vrcholy grafu na~následujícím obrázku písmeny A, B, C, D. Pokud bychom chtìli tento graf uchovat v~pamìti poèítaèe, máme na~výbìr hned nìkolik zpùsobù, jak to udìlat. -\figure{img1_stvorec.eps}{}{\epsfxsize} - +\figure{imgn_o4.eps}{}{\epsfxsize} \s{1. matice sousednosti} Matice sousednosti pro graf $G$ na~$n$ vrcholech je ètvercové pole $A$ o velikosti $n \times n$, jeho¾ prvky na @@ -58,20 +60,20 @@ $$ A_{i,j} = \left\{ \matrix {1 \Leftrightarrow \{i,j\} \in E \cr } \right.$$ -Na~pozicích $i,j$ je jednièka, pokud v~grafu $G$ vede hrana z~vrcholu $i$ do~vrcholu $j$, jinak to je nula. +Na~pozicích $i,j$ je jednièka, pokud v~grafu $G$ vede hrana z~vrcholu~$i$ do~vrcholu~$j$, jinak to je nula. Ná¹ graf z~obrázku vý¹e by tedy v~maticové reprezentaci vypadal takto: $$\bordermatrix{ & A & B & C & D\cr A & 0 & 1 & 1 & 0\cr -B & 1 & 0 & 1 & 1\cr -C & 1 & 1 & 0 & 1\cr -D & 0 & 1 & 1 & 0\cr +B & 0 & 0 & 0 & 1\cr +C & 0 & 0 & 0 & 1\cr +D & 1 & 1 & 0 & 0\cr }$$ S touto maticí se pracuje velmi snadno, napø. v¹echny sousedy $i$-tého vrcholu zjistíme jednodu¹e tak, ¾e projdeme $i$-tý øádek matice. -Má ov¹em dvì zøejmé nevýhody: èasovou a pamì»ovou slo¾itost. Projití sousedù jednoho vrcholu trvá v¾dy $\Theta(n)$, projití sousedù pro v¹echny vrcholy (co¾ potøebujeme v~BFS) pak trvá $\Theta(n^2)$. Velikost matice je v¾dy $n \times n$, bez ohledu na~to, jak \uv{øídký} je graf. U grafu s mnoha vrcholy, ale s malým poètem hran, tedy budeme zbyteènì plýtvat místem v~pamìti. Tato reprezentace je tedy nevýhodná pøedev¹ím pro tøídy grafù jako jsou stromy, které mají $n-1$ hran nebo rovinné grafy, které mají nejvý¹e $3n-6$ hran. +Má ov¹em dvì zøejmé nevýhody: èasovou a pamì»ovou slo¾itost. Projití sousedù jednoho vrcholu trvá v¾dy $\Theta(n)$, projití sousedù pro v¹echny vrcholy (co¾ potøebujeme v~BFS) pak trvá $\Theta(n^2)$. Velikost matice je v¾dy $n \times n$, bez ohledu na~to, jak \uv{øídký} je graf. U grafu s mnoha vrcholy, ale s malým poètem hran, tedy budeme zbyteènì plýtvat místem v~pamìti. Tato reprezentace je tedy nevýhodná pøedev¹ím pro tøídy grafù jako jsou stromy, které mají $n-1$ hran, nebo rovinné grafy, které mají nejvý¹e $3n-6$ hran. \s{Pozorování:} BFS s reprezentací maticí sousednosti bì¾í v~èase: $\Theta(n^2)$. @@ -81,12 +83,12 @@ U \s{2. seznam sousedù} -V~matici sousednosti jsme tedy museli procházet jak hrany, tak nehrany, co¾ bylo zbyteèné. Bylo by tedy výhodnìj¹í, pamatovat si pro ka¾dý vrchol pouze jeho sousedy. To mù¾eme zaøídit napøíklad jedním ze~dvou následujících zpùsobù: +V~matici sousednosti jsme museli procházet jak hrany, tak nehrany, co¾ bylo zbyteèné. Bylo by tedy výhodnìj¹í pamatovat si pro ka¾dý vrchol pouze jeho sousedy. To mù¾eme zaøídit napøíklad jedním ze~dvou následujících zpùsobù: -Budeme si uchovávat pole indexované vrcholy, pøièem¾ v~ka¾dém prvku pole bude ukazatel na~spojový seznam sousedù tohoto vrcholu. Tedy $L(v)={w: vw \in E(G)}$. +Uchovávejme pole indexované vrcholy tak, ¾e v~ka¾dém prvku pole je ukazatel na~spojový seznam sousedù tohoto vrcholu. Tedy $L(v)=\{w: vw \in E(G)\}$. -Pokud se nám nebude chtít pracovat se spojovými seznamy, mù¾eme vyu¾ít reprezentaci pomocí dvou polí: polem vrcholù $V(G)$, jeho¾ prvky postupnì pro ka¾dý vrchol udávají index zaèátku odpovídajícího úseku v~druhém poli $E(G)$, ve~kterém jsou ulo¾eni jeho sousedé. Pak tedy hrany z~vrcholu $i$ \uv{bydlí} v~poli $E$ a~to na~pozicích $V[i] \dots V[i+1]-1$. -\figure{img4_susedia.eps}{Znázornìní polí seznamu sousedù.}{\epsfxsize} +Pokud se nám nebude chtít pracovat se spojovými seznamy, mù¾eme vyu¾ít reprezentaci pomocí dvou polí. První pole~$V$ bude opìt indexované vrcholy. V~druhém poli~$E$ budou pro ka¾dý vrchol ulo¾eni jeho sousedé. V~poli~$V$ si pamatujeme pro ka¾dý vrchol~$i$ index do~pole~$E$, kde zaèínají jeho sousedé. K sousedùm vrcholu~$i$ se tedy dostaneme ji¾ snadno - nalezneme je na pozicích $V[i]~\dots~V[i+1]-1$. +\figure{imgn_nei.eps}{Znázornìní polí seznamu sousedù.}{\epsfxsize} Na tuto reprezentaci u¾ staèí prostor $O(n + m)$, co¾ u¾ je, na~rozdíl od~pøedchozího kvadratického prostoru, docela pøíjemné. @@ -95,12 +97,12 @@ Na tuto reprezentaci u \proof Algoritmus vezme ka¾dý vrchol i ka¾dou hranu do~ruky nejvý¹e jednou. Èasová slo¾itost bude tedy: -$$\Theta(n+\sum_{v\in V(G)} {\rm deg}(v)) = \Theta(n+m).$$ +$$\Theta\left(n+\sum_{v\in V(G)} {\rm deg}(v)\right) = \Theta(n+m).$$ \qed \s{3. orákulum} -Dal¹í mo¾ností reprezentace je pak jakési orákulum, které nám øekne (spoèítá), kam vedou hrany z~daného vrcholu\dots +Dal¹í mo¾ností reprezentace je pak jakési orákulum, které nám øekne (spoèítá), kam vedou hrany z~daného vrcholu\dots To se hodí napøíklad tehdy, pokud si nepotøebujeme pamatovat celý graf, ale staèí nám naleznout sousedy nìjakého vrcholu, které orákulum jednoznaènì výpoètem doká¾e urèit. Napøíklad pøi øe¹ení známé úlohy odmìøení daného mno¾ství vody za pomocí nádob rùzných objemù mù¾eme tento zpùsob reprezentace grafu pou¾ít. Problém pøevedeme na prohledávání grafu do~¹íøky, kde vrcholùm odpovídají jednotlivé stavy. Stav øíká, kolik vody je zrovna ve které nádobì. Potom nám ji¾ staèí ze zadaného poèáteèního vrcholu (stavu) najít cestu do~cílového. Orákulum je zde vlastnì funkce, které pøedáme vrchol a ona nám vrátí v¹echny vrcholy sousední -- tedy takové stavy, ke kterým dojde, kdy¾ vyzkou¹í v¹echny mo¾nosti pøelití kapaliny z jedné nádoby do~druhé. \h{Roz¹íøení algoritmu:} @@ -109,7 +111,7 @@ Abychom mohli vyu V~poli $D$ bude pro ka¾dý vrchol ulo¾ena vzdálenost od~poèáteèního vrcholu. V~poli $P$ si budeme pro ka¾dý vrchol pamatovat jeho pøedchùdce. Dále budeme vyu¾ívat fáze bìhu algoritmu, které budou simulovat onu vlnu: -\s{Definice {\I Fáze bìhu algoritmu}:} Ve~fázi $F_0$ je zpracováván vrchol $v_0$. Ve~fázi $F_{i+1}$ jsou zpracovávány vrcholy ulo¾ené do~fronty $Q$ bìhem fáze $F_i$. +\s{Definice: {\I Fáze bìhu algoritmu}:} Ve~fázi $F_0$ je zpracováván vrchol $v_0$. Ve~fázi $F_{i+1}$ jsou zpracovávány vrcholy ulo¾ené do~fronty $Q$ bìhem fáze $F_i$. \s{Roz¹íøený algoritmus:} \algo @@ -123,15 +125,16 @@ V~poli $P$ si budeme pro ka \::::Pøidáme $w$ do~$Q$. \endalgo -\s{Lemma:} Na~konci BFS pro v¹echny vrcholy dosa¾itelné z~$v_0$ platí, ¾e vrchol $v$ byl zpracován ve~fázi $F_i$ právì tehdy, kdy¾ vzdálenost $v_0$ a $v$ (délka nejkrat¹í cesty z~$v_0$ do~$v$) je rovna $i$. Formálnì zapsáno: $v \in F_i \Leftrightarrow d(v_0,v) = i$. +\s{Lemma:} Na~konci BFS pro v¹echny vrcholy dosa¾itelné z~$v_0$ platí, ¾e vrchol $v$ byl zpracován ve~fázi $F_i$ právì tehdy, kdy¾ vzdálenost $v_0$ a $v$ (délka nejkrat¹í cesty z~$v_0$ do~$v$) je rovna $i$. Formálnì zapsáno: $v \in F_i \Leftrightarrow d(v_0,v) = i$. (Kde $d(x,y)$ je délka nejkrat¹í cesty z~$x$ do~$y$). \proof \uv{$\Longrightarrow$}: Dùkaz provedeme indukcí podle $i$ (èísla fáze bìhu algoritmu). -První krok indukce je triviální, nebo» ve~fázi $F_0$ je oznaèen (dle definice) pouze vrchol $v_0$ a ten je od vrcholu $v_0$ vzdálen 0. +První krok indukce je triviální, nebo» ve~fázi $F_0$ je oznaèen (dle definice) pouze vrchol $v_0$ a to je jediný vrchol vzdálený~0 od~$v_0$. + +Pokud je vrchol $v$ zpracováván ve~fázi $F_i$, pak musel být zaøazen do~fronty bìhem fáze $F_{i-1}$ jako soused nìjakého vrcholu $u$. Pro vrchol $u$ mù¾eme pou¾ít indukèní pøedpoklad, tedy ¾e délka nejkrat¹í cesty z~$v_0$ do~$u$ je $d(v_0,u)=i-1$. Pak tedy $d(v_0,v)\leq i$, nebo» je¹tì nevíme, zda cesta $v_0, \dots, u, v$ je nejkrat¹í. Kdyby ale existovala nìjaká krat¹í, tedy délky nejvý¹e $i-1$, tak by byl vrchol $v$ objeven u¾ døíve ne¾ ve fázi $F_i$. Proto $d(v_0,v) = i$. -Pokud je vrchol $v$ zpracováván ve~fázi $F_i$, pak musel být zaøazen do fronty bìhem fáze $F_i-1$ jako soused nìjakého vrcholu $u$. Pro vrchol $u$ mù¾eme pou¾ít indukèní pøedpoklad, tedy ¾e délka nejkrat¹í cesty z $v_0$ do~$u$ je $d(v_0,u)=i-1$. Pak tedy $d(v_0,v)=i$. \uv{$\Longleftarrow$}: Ka¾dý dosa¾itelný vrchol padne do~nìjaké fáze (viz. minulé lemma). \qed @@ -141,7 +144,10 @@ Ji Zároveò nás mù¾e zajímat, jak bychom nejkrat¹í cestu z~$v_0$ do~$v_i$ rekonstruovali. Pro tento úèel jsme si zavedli pole $P$. Nejkrat¹í cesta z~$v_0$ do~$v_i$ bude v~obráceném poøadí vypadat: $v_i, P[v_i], P[P[v_i]], P[P[P[v_i]]], \dots, v_0$. -\s{Pozorování:} $v_0v_1,...,v_{k-1}$ je nejkrat¹í cesta z~$v_0$ do~$v_{k-1}$ +\s{Pozorování:} Pokud víme, ¾e $v_0, v_1, \dots, v_{k-1}, v_k$ je nejkrat¹í cesta z~$v_0$ do~$v_k$, pak $v_0,v_1,\dots,v_{k-1}$ je nejkrat¹í cesta z~$v_0$ do~$v_{k-1}$. Neboli prefix nejkrat¹í cesty je nejkrat¹í cesta. + +\proof +Kdyby existovala krat¹í cesta z~$v_0$ do~$v_{k-1}$, pak bychom mohli zkrátit i cestu z~$v_0$ do~$v_k$. \s{Pozorování:} BFS u~neorientovaného grafu projde celou komponentu souvislosti. @@ -152,8 +158,15 @@ V \s{Pozorování:} Pokud BFS postupnì spou¹tíme na~dosud neobarvené vrcholy v~ neorientovaném grafu, nalezneme nakonec v~èase $\Theta(n+m)$ v¹echny komponenty souvislosti. +\s{Algoritmus:} +\algo +\:Pro v¹echny vrcholy $v \in V(G)$ opakuj: +\::Pokud je vrchol $v$ neobarvený $ \Rightarrow \$. +\endalgo + \proof -Ka¾dým spu¹tìním na~dosud neobarvený vrchol neorientovaného grafu obarvíme právì jednu komponentu souvislosti (tu, ve~které je tento vrchol). Jeliko¾ postupnì projdeme v¹echny vrcholy, obarvíme nakonec také v¹echny komponenty souvislosti. Èasová slo¾itost bude stejná jako u~samotného BFS, tedy $\Theta(n + m)$. +Ka¾dým spu¹tìním na~dosud neobarvený vrchol neorientovaného grafu obarvíme právì jednu komponentu souvislosti (tu, ve~které je tento vrchol). +Postupnì projdeme v¹echny vrcholy od prvního k poslednímu a v¾dy pokud je vrchol neobarvený, spustíme na nìj BFS. Tak nakonec obarvíme v¹echny komponenty souvislosti. Èasová slo¾itost bude stejná jako u~samotného BFS, tedy $\Theta(n + m)$. \qed \s{Vìta:} $BFS(v_0)$ v~èase $\Theta(n + m)$ spoète: @@ -163,19 +176,24 @@ Ka \:strom nejkrat¹ích cest z~$v_0$ \endlist +\s{Poznámka:} Algoritmus na prohledávání do~¹íøky bude fungovat i na neorientovaném grafu. Mù¾eme si jednodu¹e pøedstavit, ¾e je to orientovaný graf, kde ka¾dá hrana má oboustrannou orientaci. + + Prohledávání do~¹íøky ale není jediný algoritmus, který nìjak systematicky prochází graf. Jak u¾ název kapitoly napovídá, budeme se zabývat je¹tì druhým algoritmem, prohledáváním do~hloubky. Podívejme se, jak bude vypadat \dots -\h{Prohledávání do~hloubky (DFS) {\I Depth First Search} } +\h{Prohledávání do~hloubky (DFS) {\I Depth-First Search} } + +Tento algoritmus neprochází graf ve~vlnì jako BFS, ale prochází ho rekurzivnì. V¾dy se zanoøí co nejhloubìji a¾ do~listu a pak se o~kus vrátí a opìt se sna¾í zanoøit. Vrcholy, ve kterých u¾ byl, ignoruje. -Tento algoritmus neprochází graf ve~vlnì jako BFS, ale prochází graf rekurzivnì. V¾dy se zanoøí co nejhloubìji a¾ do~listu a pak se o~kus vrátí a opìt se sna¾í zanoøit. Vrcholy, ve kterých u¾ byl, ignoruje. +Opìt uva¾me nejdøíve graf orientovaný. Následnì si uká¾eme, ¾e v~neorientovaném grafu budou pouze malé zmìny. -Budeme pou¾ívat podobné znaèení jako u~BFS. V poli $Z$ si budeme pamatovat, zda jsme vrchol ji¾ nav¹tívili (hodnota 1), nebo ne (hodnota 0). Navíc promìnná $T$ bude znaèit dobu bìhu algoritmu. Pøi ka¾dém nalezení nového vrcholu, èi jeho opu¹tìní, pak tuto promìnnou zvý¹íme o~1. V~poli $\$ a $\$ bude èas (prvního) nalezení a opu¹tìní vrcholu. +Budeme pou¾ívat podobné znaèení jako u~BFS. V~poli $Z$ si budeme pamatovat, zda jsme vrchol ji¾ nav¹tívili (hodnota 1), nebo ne (hodnota 0). Navíc promìnná~$T$ bude znaèit dobu bìhu algoritmu - tedy jakési \uv{hodiny}. Pøi ka¾dém nalezení nového vrcholu èi jeho opu¹tìní tuto promìnnou zvý¹íme o~1. Do~polí $\$ a $\$ si budeme ukládat èas (prvního) nalezení a opu¹tìní vrcholu. \s{Algoritmus:} \algo \: inicializace: $Z[*] \leftarrow 0, T \leftarrow 1, \[*] \leftarrow ?, \[*] \leftarrow ?$ -\: $DFS(v): Z[v] \leftarrow 1, in[v] \leftarrow T|++|$ +\: $DFS(v): Z[v] \leftarrow 1, \[v] \leftarrow T|++|$ \:: Pro $w$: $vw \in E(G)$: \::: Pokud $Z[w]=0 \Rightarrow DFS(w)$ \:: $out[v] \leftarrow T|++|$ @@ -191,28 +209,19 @@ V anal \figure{img5_dfso.eps}{Graf a znázornìní prùbìhu DFS s~jednotlivými hranami:}{\epsfxsize} -Mù¾eme si v¹imnout, ¾e jak DFS prochází graf, tak rozdìluje hrany do~4 skupin: +Mù¾eme si v¹imnout, ¾e jak DFS prochází graf, rozdìluje hrany do~4 skupin: hrany {\I stromové, zpìtné, dopøedné a pøíèné}. -\s{Typy hran ($v \rightarrow w$):} - -\itemize\ibull -\:Stromové hrany ... po nich DFS pro¹lo $\{(A \rightarrow B), (B \rightarrow C), (B \rightarrow D)\}$ -\:Zpìtné hrany $<<>_v>_w$... vedou do~pøedchùdce $v$ ve~stromu $\{(C \rightarrow A)\}$ -\:Dopøedné hrany $<<>_w>_v$... vedou do~potomka $v$ $\{(A \rightarrow D)\}$ -\:Pøíèné hrany $<>_w<>_v$... vedou do~vrcholu $v$ v~sousedním podstromì, v¾dy zprava doleva $\{(D \rightarrow A)\}$ -\endlist - -Jedinì stromové hrany jsou takové, ¾e se po~nich DFS opravdu vydá. Vedou toti¾ do~vrcholu, který nebyl dosud objeven. V~ukázkovém grafu to jsou hrany: $\{(A \rightarrow B), (B \rightarrow C), (B \rightarrow D)\}$. +Jedinì {\I stromové} hrany jsou takové, ¾e se po~nich DFS opravdu vydá. Vedou toti¾ do~vrcholu, který nebyl dosud objeven. V~ukázkovém grafu to jsou hrany: $\{(A \rightarrow B), (B \rightarrow C), (B \rightarrow D)\}$. -Pokud algoritmus objeví z~vrcholu $v$ hranu do~ji¾ døíve nav¹tíveného vrcholu $w$ a zároveò platí, ¾e $w$ je ve~stejném podstromu jako $v$, tak nazveme hranu $vw$ jako zpìtnou. Pro rozpoznání je dùle¾ité, ¾e vrchol $w$ byl ji¾ objeven, ale je¹tì ne opu¹tìn. +Pokud algoritmus objeví z~vrcholu $v$ hranu do~ji¾ døíve nav¹tíveného vrcholu $w$ a zároveò platí, ¾e $w$ je ve~stejném podstromu jako $v$, tak nazveme hranu $vw$ {\I zpìtnou}. Pro rozpoznání je dùle¾ité, ¾e vrchol $w$ byl ji¾ objeven, ale je¹tì ne opu¹tìn. V~ukázkovém grafu se jedná o hranu: $(C \rightarrow A)$. -Kdy¾ pøi prohledávání sousedù vrcholu $v$ narazíme na~vrchol $w$, který jsme ji¾ nav¹tívili, a to v~podstromì vrcholu $v$, tak nazveme hranu $vw$ jako dopøednou, nebo» vede z~$v$ do~jeho potomka. Platí tedy, ¾e jsme nejdøíve objevili vrchol $v$, potom vrchol $w$, pak jsme vrchol $w$ opustili a nyní jsme na~nìj znovu narazili po~dopøedné hranì. +Kdy¾ pøi prohledávání sousedù vrcholu $v$ narazíme na~vrchol $w$, který jsme ji¾ nav¹tívili, a to v~podstromì vrcholu $v$, tak nazveme hranu $vw$ {\I dopøednou}, nebo» vede z~$v$ do~jeho potomka. Platí tedy, ¾e jsme nejdøíve objevili vrchol $v$, potom vrchol $w$, pak jsme vrchol $w$ opustili a nyní jsme na~nìj znovu narazili po~dopøedné hranì. V~ukázkovém grafu hrana: $(A \rightarrow D)$. -Posledním typem hran je pøíèná hrana. Ta vede do~vrcholu v~sousedním podstromì zprava doleva. V~tomto pøípadì jsme tedy nejdøíve objevili vrchol $w$, ten jsme následnì opustili a a¾ pak jsme objevili vrchol $v$. +Posledním typem hran je {\I pøíèná} hrana. Ta vede do~vrcholu v~sousedním podstromì zprava doleva. V~tomto pøípadì jsme tedy nejdøíve objevili vrchol $w$, ten jsme následnì opustili a a¾ pak jsme objevili vrchol $v$. V~ukázkovém grafu to je hrana: $(D \rightarrow C)$. \s{K zamy¹lení:} Proè nemohou vést pøíèné hrany také zleva doprava? -K~rozpoznávání typù hran se nám tedy velmi hodí pole $\$ a $\$, ve~kterých si pamatujeme èas objevení a opu¹tìní vrcholu. Podle toho, jak se intervaly objevení a opu¹tìní obou vrcholù pøekrývají, mù¾eme jednoznaènì rozhodnout, o jaký typ hrany se jedná: +K~rozpoznávání typù hran se nám tedy velmi hodí pole $\$ a $\$, ve~kterých si pamatujeme èasy objevení a opu¹tìní vrcholu. Podle toho, jak se intervaly objevení a opu¹tìní obou vrcholù pøekrývají, mù¾eme jednoznaènì rozhodnout, o jaký typ hrany se jedná: U~zpìtných hran je poøadí: $\(w)$, $\(v)$, $\(v)$, $\(w)$. Intervaly do~sebe budou zanoøené takto: $<<>_v>_w$. @@ -222,8 +231,19 @@ U~p Pozn: Pou¾íváme zde toto znaèení: $<>_v = $. Jedná se o interval objevení a opu¹tìní vrcholu $v$. +\s{Typy hran ($v \rightarrow w$):} + +\itemize\ibull +\:Stromové hrany \dots po nich DFS pro¹lo. $\{(A \rightarrow B), (B \rightarrow C), (B \rightarrow D)\}$ +\:Zpìtné hrany $<<>_v>_w$\dots vedou do~pøedchùdce $v$ ve~stromu. $\{(C \rightarrow A)\}$ +\:Dopøedné hrany $<<>_w>_v$\dots vedou do~potomka. $v$ $\{(A \rightarrow D)\}$ +\:Pøíèné hrany $<>_w<>_v$\dots vedou do~vrcholu $v$ v~sousedním podstromì, v¾dy zprava doleva. $\{(D \rightarrow A)\}$ +\endlist + \s{Pozorování:} Hrany, po~kterých DFS pro¹lo, tvoøí DFS strom. -\s{Pozorování:} Intervaly ($\(v)$, $\(v)$) $\forall v \in V(G) $ tvoøí dobré uzávorkování. (intervaly synù disjunktnì vyplòují otce $\Rightarrow$ intervaly se nemohou køí¾it). +\s{Pozorování:} Intervaly ($\(v)$, $\(v)$) $\forall v \in V(G) $ tvoøí dobré uzávorkování. (Intervaly synù disjunktnì vyplòují otce $\Rightarrow$ intervaly se nemohou køí¾it). + +Nakonec si je¹tì uvìdomme, jak bude vypadat prohledávání do~hloubky na~neorientovaném grafu. Algortimus bude úplnì stejný, jenom se nám zredukuje poèet typù hran na~dvì: {\I stromové} a~{\I zpìtné}. Ani {\I dopøedné} ani {\I pøíèné} nebudou existovat, nebo» se z~{\I pøíèných} stanou {\I stromové} a z~{\I dopøedných zpìtné}. \bye diff --git a/3-dfs/imgn_nei.eps b/3-dfs/imgn_nei.eps new file mode 100644 index 0000000..75ec44a --- /dev/null +++ b/3-dfs/imgn_nei.eps @@ -0,0 +1,457 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: Ipelib 60030 (Ipe 6.0 preview 30) +%%CreationDate: D:20090612221459 +%%LanguageLevel: 2 +%%BoundingBox: 49 297 147 360 +%%HiResBoundingBox: 49.5343 297.934 146.473 359.966 +%%DocumentSuppliedResources: font QPRPPC+CMR10 +%%EndComments +%%BeginProlog +%%BeginResource: procset ipe 6.0 60030 +/ipe 40 dict def ipe begin +/np { newpath } def +/m { moveto } def +/l { lineto } def +/c { curveto } def +/h { closepath } def +/re { 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto + neg 0 rlineto closepath } def +/d { setdash } def +/w { setlinewidth } def +/J { setlinecap } def +/j { setlinejoin } def +/cm { [ 7 1 roll ] concat } def +/q { gsave } def +/Q { grestore } def +/g { setgray } def +/G { setgray } def +/rg { setrgbcolor } def +/RG { setrgbcolor } def +/S { stroke } def +/f* { eofill } def +/f { fill } def +/ipeMakeFont { + exch findfont + dup length dict begin + { 1 index /FID ne { def } { pop pop } ifelse } forall + /Encoding exch def + currentdict + end + definefont pop +} def +/ipeFontSize 0 def +/Tf { dup /ipeFontSize exch store selectfont } def +/Td { translate } def +/BT { gsave } def +/ET { grestore } def +/TJ { 0 0 moveto { dup type /stringtype eq + { show } { ipeFontSize mul -0.001 mul 0 rmoveto } ifelse +} forall } def +end +%%EndResource +%%EndProlog +%%BeginSetup +ipe begin +%%BeginResource: font QPRPPC+CMR10 +%!PS-AdobeFont-1.1: CMR10 1.00B +%%CreationDate: 1992 Feb 19 19:54:52 +% Copyright (C) 1997 American Mathematical Society. All Rights Reserved. +11 dict begin +/FontInfo 7 dict dup begin +/version (1.00B) readonly def +/Notice (Copyright (C) 1997 American Mathematical Society. All Rights Reserved) readonly def +/FullName (CMR10) readonly def +/FamilyName (Computer Modern) readonly def +/Weight (Medium) readonly def +/ItalicAngle 0 def +/isFixedPitch false def +end readonly def +/FontName /QPRPPC+CMR10 def +/PaintType 0 def +/FontType 1 def +/FontMatrix [0.001 0 0 0.001 0 0] readonly def +/Encoding 256 array +0 1 255 {1 index exch /.notdef put} for +dup 65 /A put +dup 66 /B put +dup 67 /C put +dup 68 /D put +dup 69 /E put +dup 86 /V put +dup 58 /colon put +dup 53 /five put +dup 52 /four put +dup 49 /one put +dup 51 /three put +readonly def +/FontBBox{-251 -250 1009 969}readonly def +currentdict end +currentfile eexec +d9d66f633b846a97b686a97e45a3d0aa052a014267b7904eb3c0d3bd0b83d891 +016ca6ca4b712adeb258faab9a130ee605e61f77fc1b738abc7c51cd46ef8171 +9098d5fee67660e69a7ab91b58f29a4d79e57022f783eb0fbbb6d4f4ec35014f +d2decba99459a4c59df0c6eba150284454e707dc2100c15b76b4c19b84363758 +469a6c558785b226332152109871a9883487dd7710949204ddcf837e6a8708b8 +2bdbf16fbc7512faa308a093fe5cf7158f1163bc1f3352e22a1452e73feca8a4 +87100fb1ffc4c8af409b2067537220e605da0852ca49839e1386af9d7a1a455f +d1f017ce45884d76ef2cb9bc5821fd25365ddea6e45f332b5f68a44ad8a530f0 +92a36fac8d27f9087afeea2096f839a2bc4b937f24e080ef7c0f9374a18d565c +295a05210db96a23175ac59a9bd0147a310ef49c551a417e0a22703f94ff7b75 +409a5d417da6730a69e310fa6a4229fc7e4f620b0fc4c63c50e99e179eb51e4c +4bc45217722f1e8e40f1e1428e792eafe05c5a50d38c52114dfcd24d54027cbf +2512dd116f0463de4052a7ad53b641a27e81e481947884ce35661b49153fa19e +0a2a860c7b61558671303de6ae06a80e4e450e17067676e6bbb42a9a24acbc3e +b0ca7b7a3bfea84fed39ccfb6d545bb2bcc49e5e16976407ab9d94556cd4f008 +24ef579b6800b6dc3aaf840b3fc6822872368e3b4274dd06ca36af8f6346c11b +43c772cc242f3b212c4bd7018d71a1a74c9a94ed0093a5fb6557f4e0751047af +d72098eca301b8ae68110f983796e581f106144951df5b750432a230fda3b575 +5a38b5e7972aabc12306a01a99fcf8189d71b8dbf49550baea9cf1b97cbfc7cc +96498ecc938b1a1710b670657de923a659db8757147b140a48067328e7e3f9c3 +7d1888b284904301450ce0bc15eeea00e48ccd6388f3fc3a3b198747b4dc992e +839a610506453ba7b2a56b2c552fdbe23916074dd54d39ed27a52d90d5d74b07 +a5265e72e3f2e0acd9513e056f15e4bcbb9f409a6f39deae8d919c80ec13c56f +4864a6ccff1acfda3d992f46d45571fc760dff6ebfb011b6c123167ca96b77a0 +cfa8861be3814e002e0a571e62c497886a135acb53c0acf7fecceef3fa4dc436 +9115af71c9ca5e9e71caaf5a17d5598d8e8bb772ef73e44f07bfcea039dfb0f7 +e2c38f138ee0922fbdd3d7ba9cd9676102b0b9e22a4744edbf299db408b7b0b9 +b66dc8bdb8552ba01aee38e1205b077c2f2c646747c748125f1ccf350e3930ad +ae5249b3d5cae219454906c86eab1df73eec1e8afa68c7e230dad77d9a072873 +b96e9def3eaec6d5b9a045f9280d79ac9e0857ac916fc29db487a669486de827 +dfa3c487fbaebcbbcb9558497a66ce72491373354376aef7374ae1d709ec9ce1 +244e5cc8e7b40f9a2d36fbaa585e2265e0d4491f56166c30155a359ddb814235 +88d830822cf1827dd0b979e7f899a31e7570692e6a8eff1fbba5de09e2fc63c2 +934eda05d28cb4ed0a2804ca36d4619d88831a4ab00bdb2a8072edd1670ecd13 +87284ffdc14c464b15fefe5f5d17dd99a9c291a98fc3cd46a47764358d7d65d2 +da2a30960687f2dcf03e8ec3b3355440f87909ff158b8a851e1b210c3aab5a51 +451da27dd7da80feb166c3db5debd271270a478aed9640392137548da4060fa2 +2c764e0b6b9844980a089f0db4798087f2b4f9e15cbcc2b4b15da7f10d8dcf4a +96714fb8c4c3b8ec48d54aa658190a40ecbef817e6eff5db4181bf7dc7a13bf3 +f6a16435be39717749e237776b1cfbb090758a477f70be0c69b1ef937795fdbc +585fcdd4af78ae484b761bfc3661d687bb1a64f4ea8274af10dd73b7575d67e6 +78d78a9802fce8dd84d1006acdc3fdb82b18978ae78311ec7e57be059ce186c6 +e48830c45dac72f5f8661a57909384e6c4447b21340a4b05412f00865d53a4de +e0c47d4d3cb422399d88bf504f73094546c121fcfdf04fa7cb4962550134e3f6 +47eeea66e9dfd5998bf15055f858ed062d58ba72274ac6653317786f5e2042e5 +d4cd6fd151f7ad1d25517ed6d873a8bb4bf1789618bf224d3a3b2545982782bb +32e9c9b522abb351563d90f75154918a160bfcaae19ab1e61ce635a4004a912e +65ca0b2f3a4bd0207820edd437a307b7cfa74fc61e39283f38a8ad579fa4e5db +ce594480fb400b3a2aa034b9d2355e52e51f2dcd3c4809f0734ac964b93cc881 +c0c870304d83613d1f47f48b90d5b98538d08087144e573824a367e7d3efca97 +6bfd34799e6745358549b6fee54f708740b519578f21c667c0c381a89706c312 +a312ed8c10f96d2e8fae3b42313a09bdf601ea61373eff6e912dc93ba8ce55a9 +925ebbaa324e5c3c69e3ffebe71dc1c697bbc78c08f7981d03329cc648cd9289 +8c4e0a259895e741a5896b5c64468f95ddda059949e08dde8dcb8c937e8781c5 +683282986f90939e25fcab8db330bdd2db287554de19b78d8e9071256e1c5aff +8e21b522d852423cdaf38d1adce8482f076e6bc95f713d2e2637e2a192da02a1 +f677fcffaec9afff27e64e7d2e30aaa8a2ff2fb3b989da85c63a65bee2b05817 +4414dc2725db959992e4ffd3f9774c77e1b718eb56472bac7932eaef435a2f6f +e9c55380631a6c2c82666a5cc57219f679878349e7cfddfdb70f6b3c37ac95c3 +12c347be66e8aa46dbf239631922e4ac8fab0dac8a4553d73ee04ab3da50d44f +b2f39132ed5d8823017dd4a28c9140437ae367e1d20af64c350b4f1bb50ed4ba +6b7cbe3ee65a2ef32b0358cdd5b7ffa020306e64b3b2fbb3667b0c75a3a7a873 +4cfe41e347a658be4054c9d8423fa4019db27074ad2e0e8f6207cff81f7f82f0 +fb419014928396fa9a322f53c95dfa9261c5ea4865f3ee6d1ac0647accccdbe7 +25b8e918552e8381b87fc5c77986be2a77b36d17cd5bc23df8d6b0a7dfef62f5 +42f8fe68f17d9109e6148de69e1539d681964976be07e2f04685b9527cefca58 +9e9393089bd19aec57aa167c0ce1f497ae31c960ef1384a6d32249cab28b920c +1686978ccb1ba542e2c9087789aa35a189fb2593959033466cb1dd92469127a1 +d794ce4409803179f98a79501e1dad1038bbf3f6e81cb5523db5659b4dfdf080 +94a338deaa1b0697b0cac0fc91880437e832ca30f19c7170b0bb893f83c9ccc4 +e87eefce3098487fc5e87aad1765329b459f2d0658723a11f33e336b007f7f15 +6a397ec72cbe3712ba6d6bd42840ab45c34304fc39124a863efe6f361fc4d393 +7f0b28f11fc36f3ddb11f613481dea9b394aaceddce2bca659619d63495725ec +92bb5ecacc4c221125284d4fe04d41c57f6464206b8c83186f46b0df62fe5b24 +d3932aa11c4d79e45190d51ff66bb67492a7598ba18dde7d0425c27bcbabad06 +0863abeb53800e73945f001d439d582faaeb133d93dfe061137be3aa6a978002 +4134e128d0a061ce88a587be221168d10d8c949cc390a05d0fdc41d4b24a89b7 +d9bac2c2b884aa30cbab7b09689c8cedb68b0afb20631cb7305ca3260134a3e1 +9aa5bdf928d303183790ea6ff5b15df78a03a5aaaa74382721ceaa50c382d095 +6921e0e64a7cbc1b50ac285569c5efaa0aae56bf3755a36825d162e1649a77f6 +e6f7c41a5b281c43eadf2a90a743e3cd209ca0748716145fb87f57aa3b5ebf43 +96c5ce112c88956ae37ddae0bd254aba4f1f08d9a59934f2d4241732bd34b728 +10978c04d5dd04c20df81a2bff3d1befde4393382e7b99e364eab9702e0bd5f9 +47205de80f0d5d4156ae85c493a162124b76efeca55f33ca176baff8ea009c01 +ce30dfc9e54065321e0a862d825bc7c5d1d094599ade3cf94e9d7279953ff1d2 +fbd4b0f366d9a25634474ae202a5c14565f93b473e80cb09da4a16aeffeb4df5 +119b2aebdf8da0cf074f18d664d0188ec7e1c397dfa128b8c6c2168879c40da8 +3f4012ba83b665ab462c2f031b5cfe696647a3f8b718a1f6dfd226e8a464962a +da08dda0facd6f366b2c2ae6f8fbf35bac0e33574779a87f05f0a019460407d9 +bb357e58e5cbc8492aeff30f973fa4bf4dd36d2e78f68c3133df39d3502bd3b6 +92474c4d6cbbed6d3045713d9c4a43c644e0dcfee6e53e53f7b1abc99556af81 +f98b6b30d813f309883aa5d6da7f10bd3a1e4ee91ba1f83396fe036e8e87c26c +be6a9b016e7e5eadb64356c2086d8e150ce16ef4b3f4b1ae59b3ade1e5c66f9a +9d63de3ecb344346a99af40a851786fe6a2bd76b970179725de004784a0f4025 +b9eb1a0155c0dce68945b3a83137e354eaa48e0c0add1944fd77049fecba40c8 +6a01a75169b9efb433747f3f330423b58dcd98a6db30199e5e1b99cfba8c1176 +8a +00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +cleartomark +%%EndResource +/F8 /QPRPPC+CMR10 findfont definefont pop +%%EndSetup +0 J 1 j +q 0.4 w +65.0001 338.434 m +78.5662 338.434 l +78.5662 352 l +65.0001 352 l +h S +Q +q 1 0 0 1 67 353 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(A)]TJ +ET +Q +q 0.4 w +78.4961 338.434 m +92.0622 338.434 l +92.0622 352 l +78.4961 352 l +h S +Q +q 0.4 w +92.0721 338.434 m +105.638 338.434 l +105.638 352 l +92.0721 352 l +h S +Q +q 0.4 w +105.568 338.434 m +119.134 338.434 l +119.134 352 l +105.568 352 l +h S +Q +q 1 0 0 1 80.6523 353.157 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(B)]TJ +ET +Q +q 1 0 0 1 94.5489 353.158 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(C)]TJ +ET +Q +q 1 0 0 1 109.438 353.158 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(D)]TJ +ET +Q +q 1 0 0 1 49.5343 341.845 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(V:)]TJ +ET +Q +q 0.4 w +65.0001 298.334 m +78.5662 298.334 l +78.5662 311.9 l +65.0001 311.9 l +h S +Q +q 0.4 w +78.4961 298.334 m +92.0622 298.334 l +92.0622 311.9 l +78.4961 311.9 l +h S +Q +q 0.4 w +92.0721 298.334 m +105.638 298.334 l +105.638 311.9 l +92.0721 311.9 l +h S +Q +q 0.4 w +105.568 298.334 m +119.134 298.334 l +119.134 311.9 l +105.568 311.9 l +h S +Q +q 0.4 w +119.011 298.334 m +132.577 298.334 l +132.577 311.9 l +119.011 311.9 l +h S +Q +q 0.4 w +132.507 298.334 m +146.073 298.334 l +146.073 311.9 l +132.507 311.9 l +h S +Q +q 1 0 0 1 49.5343 301.746 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(E:)]TJ +ET +Q +q 1 0 0 1 68.3803 342.51 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.58 cm +BT +/F8 9.9626 Tf 0 785.58 Td [(1)]TJ +ET +Q +q 1 0 0 1 68.3803 301.653 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(B)]TJ +ET +Q +q 1 0 0 1 81.6312 301.653 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(C)]TJ +ET +Q +q 1 0 0 1 94.0539 301.653 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(D)]TJ +ET +Q +q 1 0 0 1 108.133 301.653 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(D)]TJ +ET +Q +q 1 0 0 1 121.66 301.653 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(A)]TJ +ET +Q +q 1 0 0 1 135.739 301.653 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(B)]TJ +ET +Q +q 1 0 0 1 82.7354 342.51 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.58 cm +BT +/F8 9.9626 Tf 0 785.58 Td [(3)]TJ +ET +Q +q 1 0 0 1 95.7103 342.51 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.58 cm +BT +/F8 9.9626 Tf 0 785.58 Td [(4)]TJ +ET +Q +q 1 0 0 1 109.513 342.51 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.58 cm +BT +/F8 9.9626 Tf 0 785.58 Td [(5)]TJ +ET +Q +q [4] 0 d +0.4 w +71.1641 337.708 m +71.1641 313.414 l +S +q [] 0 d +71.1641 313.414 m +72.8308 318.414 l +69.4975 318.414 l +h q f* Q S +Q +Q +q [4] 0 d +0.4 w +84.887 336.958 m +97.768 313.596 l +S +q [] 0 d +97.768 313.596 m +96.8133 318.78 l +93.8942 317.17 l +h q f* Q S +Q +Q +q [4] 0 d +0.4 w +98.9661 336.958 m +111.847 313.596 l +S +q [] 0 d +111.847 313.596 m +110.892 318.78 l +107.973 317.17 l +h q f* Q S +Q +Q +q [4] 0 d +0.4 w +113.045 336.958 m +125.926 313.596 l +S +q [] 0 d +125.926 313.596 m +124.971 318.78 l +122.052 317.17 l +h q f* Q S +Q +Q +showpage +%%BeginIpeXml: /FlateDecode +%GhU]8?#SFN'Sc)R/$.N9r;BKX9&$q8rINcDE$8s=;%h9"^OE@Re#h)t8EiGg,iln`kOGh'H]GYZ +%X%7E=DXqg0b7%mDARnZYd$F>Uqh@j5)6)o2bMt`OkOleo^:c,mA)_Nph-:<,4>U4J/tJ:Gfp'\X +%2ZKOJE2@tPk4A.PQ7_C-66htsfrE]3O$uHXqHLQ=X%696^23?^EL+.G\-S/#-JPc@MbmC=cqVlL +%F^7`ARY4,!mp:sQ6G)*8H61SCFa8a.o-,aRJ0!?)#99MY3lrp]l-hj&7QkCSE%\,O-6lND_mX-i +%#mJt?-;k2V\T%F8d5?#\R(fiF$53VWgA'#9ZHkVMS4pR?$G00#=;Oc>E&b=TXRMDtb[Zctqg@)" +%B:5U=MN"WH^08"u7I$8`a>-eq'/SuAOfq#3%o"VGD8ajaVtTbTY,2N(pX12!84=7Opmq=m!BSYHN9q+gVg#&DX' +%-\hi*VcpVE@eK'K0OaLuC(;Wm_sE^h^K,Se6er.7;dp"UIiI=!6__2MkEs\2e9pF)Q,^@cLh#SX +%M1l9eW8KAJ0f,>S!Fn>JTY`<32UmHL +%%EndIpeXml +%%Trailer +end +%%EOF diff --git a/3-dfs/imgn_o4.eps b/3-dfs/imgn_o4.eps new file mode 100644 index 0000000..27fcbcf --- /dev/null +++ b/3-dfs/imgn_o4.eps @@ -0,0 +1,253 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%Creator: Ipelib 60030 (Ipe 6.0 preview 30) +%%CreationDate: D:20090612215531 +%%LanguageLevel: 2 +%%BoundingBox: 19 396 116 489 +%%HiResBoundingBox: 19.515 396.99 115.567 488.793 +%%DocumentSuppliedResources: font ONQNXF+CMR10 +%%EndComments +%%BeginProlog +%%BeginResource: procset ipe 6.0 60030 +/ipe 40 dict def ipe begin +/np { newpath } def +/m { moveto } def +/l { lineto } def +/c { curveto } def +/h { closepath } def +/re { 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto + neg 0 rlineto closepath } def +/d { setdash } def +/w { setlinewidth } def +/J { setlinecap } def +/j { setlinejoin } def +/cm { [ 7 1 roll ] concat } def +/q { gsave } def +/Q { grestore } def +/g { setgray } def +/G { setgray } def +/rg { setrgbcolor } def +/RG { setrgbcolor } def +/S { stroke } def +/f* { eofill } def +/f { fill } def +/ipeMakeFont { + exch findfont + dup length dict begin + { 1 index /FID ne { def } { pop pop } ifelse } forall + /Encoding exch def + currentdict + end + definefont pop +} def +/ipeFontSize 0 def +/Tf { dup /ipeFontSize exch store selectfont } def +/Td { translate } def +/BT { gsave } def +/ET { grestore } def +/TJ { 0 0 moveto { dup type /stringtype eq + { show } { ipeFontSize mul -0.001 mul 0 rmoveto } ifelse +} forall } def +end +%%EndResource +%%EndProlog +%%BeginSetup +ipe begin +%%BeginResource: font ONQNXF+CMR10 +%!PS-AdobeFont-1.1: CMR10 1.00B +%%CreationDate: 1992 Feb 19 19:54:52 +% Copyright (C) 1997 American Mathematical Society. All Rights Reserved. +11 dict begin +/FontInfo 7 dict dup begin +/version (1.00B) readonly def +/Notice (Copyright (C) 1997 American Mathematical Society. All Rights Reserved) readonly def +/FullName (CMR10) readonly def +/FamilyName (Computer Modern) readonly def +/Weight (Medium) readonly def +/ItalicAngle 0 def +/isFixedPitch false def +end readonly def +/FontName /ONQNXF+CMR10 def +/PaintType 0 def +/FontType 1 def +/FontMatrix [0.001 0 0 0.001 0 0] readonly def +/Encoding 256 array +0 1 255 {1 index exch /.notdef put} for +dup 65 /A put +dup 66 /B put +dup 67 /C put +dup 68 /D put +readonly def +/FontBBox{-251 -250 1009 969}readonly def +currentdict end +currentfile eexec +d9d66f633b846a97b686a97e45a3d0aa052a014267b7904eb3c0d3bd0b83d891 +016ca6ca4b712adeb258faab9a130ee605e61f77fc1b738abc7c51cd46ef8171 +9098d5fee67660e69a7ab91b58f29a4d79e57022f783eb0fbbb6d4f4ec35014f +d2decba99459a4c59df0c6eba150284454e707dc2100c15b76b4c19b84363758 +469a6c558785b226332152109871a9883487dd7710949204ddcf837e6a8708b8 +2bdbf16fbc7512faa308a093fe5cf7158f1163bc1f3352e22a1452e73feca8a4 +87100fb1ffc4c8af409b2067537220e605da0852ca49839e1386af9d7a1a455f +d1f017ce45884d76ef2cb9bc5821fd25365ddea6e45f332b5f68a44ad8a530f0 +92a36fac8d27f9087afeea2096f839a2bc4b937f24e080ef7c0f9374a18d565c +295a05210db96a23175ac59a9bd0147a310ef49c551a417e0a22703f94ff7b75 +409a5d417da6730a69e310fa6a4229fc7e4f620b0fc4c63c50e99e179eb51e4c +4bc45217722f1e8e40f1e1428e792eafe05c5a50d38c52114dfcd24d54027cbf +2512dd116f0463de4052a7ad53b641a27e81e481947884ce35661b49153fa19e +0a2a860c7b61558671303de6ae06a80e4e450e17067676e6bbb42a9a24acbc3e +b0ca7b7a3bfea84fed39ccfb6d545bb2bcc49e5e16976407ab9d94556cd4f008 +24ef579b6800b6dc3aaf840b3fc6822872368e3b4274dd06ca36af8f6346c11b +43c772cc242f3b212c4bd7018d71a1a74c9a94ed0093a5fb6557f4e0751047af +d72098eca301b8ae68110f983796e581f106144951df5b750432a230fda3b575 +5a38b5e7972aabc12306a01a99fcf8189d71b8dbf49550baea9cf1b97cbfc7cc +96498ecc938b1a1710b670657de923a659db8757147b140a48067328e7e3f9c3 +7d1888b284904301450ce0bc15eeea00e48ccd6388f3fc3a3b198747b4dc992e +839a610506453ba7b2a56b2c552fdbe23916074dd54d39ed27a52d90d5d74b07 +a5265e72e3f2e0acd9513e056f15e4bcbb9f409a6f39deae8d919c80ec13c56f +4864a6ccff1acfda3d992f46d45571fc760dff6ebfb011b6c123167ca96b77a0 +cfa8861be3814e002e0a571e62c497886a135acb53c0acf7fecceef3fa4dc436 +9115af71c9ca5e9e71caaf5a17d5598d8e8bb772ef73e44f07bfcea039dfb0f7 +e2c38f138ee0922fbdd3d7ba9cd9676102b0b9e22a4744edbf299db408b7b0b9 +b66dc8bdb8552ba01aee38e1205b077c2f2c646747c748125f1ccf350e3930ad +ae5249b3d5cae219454906c86eab1df73eec1e8afa68c7e230dad77d9a072873 +b96e9def3eaec6d5b9a045f9280d79ac9e0857ac916fc29db487a669486de827 +dfa3c487fbaebcbbcb9558497a66ce72491373354376aef7374ae1d709ec9a16 +4c369c237dd28fc4be2843036e872b2a008d0ddea0146e9e5f0ef49715bdcdab +d4efa0bd65c6822d70b0fbd115be7ebce816ab40d2ecdb17e15f2adb75a84589 +be79a66e6c29ace5156971c30e226b3fc1a7cbfe350c693b23476c3c77f0d214 +06751d2decca6d14a899c877a1f71cf5f205c8ff35460b3792108c17a29a339f +99a0be9fc33a702d808aab91fd490e6e8c0d59356d2b2cd44371d02d3d040d8f +121ce31ccece5ddae9c44e87f9139deb1ab6d393e6eadb7a3a33b4217523ec3f +fec90d8b22e6ccbe26b11e71f55ed334888ac82ad91c436891db5661343dfd21 +45312879ec8d7683212cde2995795e39d4675e000110da0432e48b67649a1b26 +4987a5eca0e6a22e78449eb3c8fd551c4e5e87a6054f1c5971ef8ff30f2783ee +a5ff2ea77e69b9941d2dbce8a5925612d11b11a7df8bd2f330b197b3dd86c24b +fc572da77bbfb6af2188ee8dd14cf4ade307fa46d9b8d22aeb35a43f06b5821b +9e482756623e2f0140d7098532257572404be051e8df6f02f84bfea203c615fa +fcecfeccb003b823def3067c1997219f65806a8773058cd3424d7c7cd0cf374a +e86fce217b3bf9aa401c2dd821dd46b39379c8b52c6036ec0f40f93a28c315e5 +ead19ea0801900ccd6ac97146e65ca89d2867893229462bf170182af3e77b420 +2bbb41906d120ed411c876185c41a0372b8ddfe0e8625fcd3e404f9c044620bd +71c507c4d00bcb084d603f7a14b080d45636acf5e6a650ee2085a677551c09dd +32c78015d76bb8f2f2da0eab87ee1a7d85c74b8b77f6ce17635a52c38156d333 +ab3d45276fe6e5b54ade0a1e88182b17520412533a15e7f589117836d5ab87ab +b39b71b7322990f215dbf76876266c309ddae6e644a9d8e5db424962962bd8a0 +d63f41db64526d791ba810a40c52c2f8c6824883c80adb7319a6a789a6284fe3 +8540c49bd012c615e9884a94e4cc8abed89c93bfc593e096f2d2a0503a517103 +59010b87a61e0cf19bcb639df479d7cd66bfc21e654d798eca1a2fe47a895b07 +16410efbe3e70dbed8059b584a7e3c7a1e8dd8b59f4b185715cd1a558a3fccd2 +f4f46d7eb073a7d5db4c302e25421cb49666e97660f8884c760ea1777df5b552 +a97193acae48bfaef59477bf56ef0a119fb48ab70e6d96edb07d71f731e0d4fe +3181d8d39ebec0da4dfc85cf47408ec49bc65bea2ca37a292d16c00955f12017 +76ea1f3e853813cbd0a712e3500da4072fd738087710abfded16c53d1beb6bc6 +cf4a09593a33440859d4689070b8edc1bd731ff68459036f51d4123f2032bd98 +9256c2d93db97af05aecd7b4b12455d6dd2aea6b7bd5bb94c0fb073523339505 +3ee6f692022ee5f56a29b65644b4d5603cc3a88423e127b23869a5623d55 +00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +cleartomark +%%EndResource +/F8 /ONQNXF+CMR10 findfont definefont pop +%%EndSetup +0 J 1 j +q 0.4 w +31.6395 407.552 m +103.142 407.574 l +S +q 103.142 407.574 m +93.141 410.904 l +93.143 404.238 l +h q f* Q S +Q +Q +q 1 0 0 1 19.515 481.985 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(A)]TJ +ET +Q +q 1 0 0 1 108.51 481.985 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(B)]TJ +ET +Q +q 1 0 0 1 19.516 396.99 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(C)]TJ +ET +Q +q 1 0 0 1 106.511 396.99 cm 1 0 0 1 0 0 cm 0 g +0 G + +1 0 0 1 0 -785.192 cm +BT +/F8 9.9626 Tf 0 785.192 Td [(D)]TJ +ET +Q +q 0.4 w +31.6395 480.548 m +103.142 480.57 l +S +q 103.142 480.57 m +93.141 483.9 l +93.143 477.234 l +h q f* Q S +Q +Q +q 0.4 w +103.365 407.476 m +103.411 480.312 l +S +q 103.411 480.312 m +100.071 470.314 l +106.738 470.31 l +h q f* Q S +Q +q 103.365 407.476 m +106.705 417.474 l +100.038 417.478 l +h q f* Q S +Q +Q +q 0.4 w +31.369 407.81 m +31.4148 480.779 l +S +q 31.369 407.81 m +34.7086 417.808 l +28.0419 417.812 l +h q f* Q S +Q +Q +q 0.4 w +31.5722 480.31 m +103.217 407.863 l +S +q 31.5722 480.31 m +36.2337 470.856 l +40.9739 475.544 l +h q f* Q S +Q +Q +showpage +%%BeginIpeXml: /FlateDecode +%GhTRUgMRrR&-1)OI)Uncj5CK52cADCoJ<^GCm;>O`NG`,?f,:?Bi<&iUEm-U+U5hm@.5B7#nEpC +%\_B'e+t@--.OgB`C"Nq'>)psrFNE\Y.!U*FaSYl&3$taHG5"EL#.-]he.s?_?+8,Rq2^ms7L9:B +%AbX]YLh5[/7@)YUOi\jI`D[^+S3\k>Yh2GLR5ZIN,0k-J9(OcJ9%5@m7OD +%e]2ZV*-E,UN2:lo6-D0h*f(iWOpQm`;(J?!!p%@p5m&oX=[d[g;`%#I8g*lFJdRe_iu.KGEk(S\ +%0"+.rV0d#\)p9Q??5RR5Z(Qa._/%]Z#[;Xh)XDYS!a82]<>'IK:ZF=(!2P[+RD_-b!)\76""iD- +%!i2WG:kQ3>U6`Xjgo&:s-:0lXosek+j4_mHD,];-7lkh]One7lf-"@L6Yu@Kp9KWEC@aVdY,5,W +%mHsW5@U=ok.htA_O\GBflG=pJ4A).jWOX?Ej5(sXp,8o"Wb)]P9%9YCW)aL1JsMX:n#oSW0^kZ` +%Iq)BA,GKifZ`;haW\m?_&[T'__rN&A2>ulTA:t&t]N.2ccKbgAV:lEs?E+B'G`s +%%EndIpeXml +%%Trailer +end +%%EOF -- 2.39.5