From a7b03ab23a84a12571d51ce85c5a0fad5c4c1c52 Mon Sep 17 00:00:00 2001 From: Jan 'Moskyt' Matejka Date: Tue, 21 Jun 2011 01:12:52 +0200 Subject: [PATCH] 4: masivni korektury --- 4-dfs/4-dfs.tex | 230 ++++++++++++++++++++++++++---------------------- 1 file changed, 123 insertions(+), 107 deletions(-) diff --git a/4-dfs/4-dfs.tex b/4-dfs/4-dfs.tex index 4b594cb..ebe9d4e 100644 --- a/4-dfs/4-dfs.tex +++ b/4-dfs/4-dfs.tex @@ -1,9 +1,95 @@ \input ../lecnotes.tex \let\la\leftarrow -\prednaska{4}{Aplikace DFS}{} +\prednaska{4}{Aplikace DFS}{do pou¾itelné podoby dokopal Jan \uv{Moskyto} Matìjka} -\h{Nejdel¹í cesta v ohodnoceném DAG-u (v grafu bez orientovaných cyklù)} +\h{Detekce cyklù v orientovaném grafu} + +Algoritmus na vypsání {\I v¹ech} cyklù v grafu si neuká¾eme, nebo» tento +problém je tì¾¹í, ne¾ se zdá. Mimo jiné proto, ¾e cyklù mù¾e být a¾ +exponenciálnì mnoho. Zde probíráme nalezení {\I nìjakého} cyklu v orientovaném +grafu. + +\s{Definice:} $\(G)$ znaèíme spu¹tìní DFS tak, aby pro¹el v¹echny vrcholy. + +Realizace pøedchozí definice je jednoduchá. +\algo +\:Dokud existuje nenav¹tívený vrchol $v$: +\::Spustíme $\(v)$. +\endalgo + +\s{Lemma:} Cyklus je v grafu $G$ právì tehdy, kdy¾ $\(G)$ oznaèí nìjakou +hranu jako zpìtnou. + +\proof Buï $v_1,v_2,\dots,v_k,v_1$ cyklus v grafu $G$ a $v_1$ buï BÚNO vrchol s +max. $\(v_i)$. Pak jistì $\(v_k) < \(v_1)$. Jakého typu je hrana +$(v_k,v_1)$? + +Uva¾me poøadí opou¹tìní vrcholù na rùzných typech hran $(x,y)$. Na +stromové, dopøedné a pøíèné hranì platí $\(x) > \(y)$, na zpìtné +$\(x) < \(y)$. Tedy $(v_k,v_1)$ musí být nutnì zpìtná. + +V opaèném smìru nalezneme pro zpìtnou hranu $(x,y)$ cestu z $y$ do $x$ po +stromových hranách. \qed + +\s{Algoritmus:} +\algo +\algin Graf $G$ +\:Spustíme $\(G)$ a pøi nalezení první zpìtné hrany $(u,v)$ zastavíme. +\:Pokud jsme nalezli zpìtnou hranu: +\::Vypí¹eme v¹echny vrcholy mezi $(u,v)$ ze zásobníku onoho DFS v opaèném poøadí. +\:jinak +\::Graf je acyklický. +\endalgo + +\s{Èasová i pamì»ová slo¾itost} je $\O(m+n)$, nebo» se jedná o triviálnì upravené DFS. + +\h{Topologické uspoøádání DAGu (grafu bez orientovaných cyklù)} + +\s{Definice:} {\it Topologické uspoøádání} acyklického orientovaného grafu $G$ o $k$ +vrcholech je ohodnocení vrcholù èísly $1\dots k$ tak, ¾e $(u,v) \in E(G) +\Rightarrow f(u) < f(v)$. + +\s{Pozorování:} Vhodné topologické uspoøádání nám dá napøíklad $\$ z +$\(G^R)$. $G^R$~budi¾ graf $G$, ve kterém otoèíme orientace v¹ech hran. + +\h{Hledání mostù v neorientovaném grafu} + +\s{Definice:} Hrana $uv \in E(G)$ je {\I most}, pokud se jejím odebráním +z~grafu $G$ zvý¹í poèet komponent souvislosti tohoto grafu. + +\s{Pozorování:} Hrana, která je v nìjakém cyklu, nemù¾e být mostem. Z cyklu +toti¾ lze libovolnì odebrat jednu hranu a pøesto zùstane souvislý. V¹echny +ostatní hrany naopak mosty jsou. + +Mù¾e být mostem jiná hrana ne¾ stromová? Zpìtné hrany nutnì tvoøí cyklus. +Pøíèné a dopøedné se v neorientovaném DFS neobjeví. + +Hledáme tedy v¹echny stromové hrany, které nejsou v ¾ádném cyklu. Projdeme graf +zase pomocí upraveného DFS. + +Kdy je hrana $uv$ v nìjakém cyklu? Kdy¾ existuje cesta $v\dots w$ (a nebo +$v=w$), zpìtná hrana $wx$ a cesta $x\dots u$ (a nebo $x=u$). + +\smallskip +\s{Algoritmus} bude je¹tì trochu více upravené DFS. Pro ka¾dý vrchol~$v$ si +budeme kromì hloubky je¹tì pamatovat $z(v)$. To bude nejmen¹í \ vrcholu, +do kterého se dá dostat po zpìtných hranách z~vrcholu $v$ nebo podstromu pod ním. + +\algo +\:Vstoupíme do vrcholu $u$ jako DFS. +\:$x \la $~minimum z $\(v)$ pøes v¹echny zpìtné hrany $uv$ +\:$y \la $~minimum ze $z(w)$ pøes v¹echny stromové hrany $uw$ +\:$z(u) \la \min xy$ +\:Pokud $z(u) \ge \(u)$, +\::je jistì mostem hrana, po které jsme vstoupili do $u$. +\endalgo + +\s{Èasová i pamì»ová slo¾itost} tohoto upraveného DFS jsou $\O(m+n)$. + +\qed + +\h{Nejdel¹í cesta v ohodnoceném DAGu} \s{Definice:} Pro $u,v \in V$ bude $D(u,v)$ délka nejdel¹í cesty z $u$ do $v$. $D^R(u,v)$ bude délka nejdel¹í cesty v grafu s otoèenými hranami. @@ -20,7 +106,7 @@ Neexistuje-li cesta z $u$ do $v$, nech $W_i = \{w_j\mid(w_j,w_i)\in E\}$. \:Pro v¹echny vrcholy $w_i$ pøed $u$ ($\forall w_i: i{\I Pozorování:} $e = (x,y)$ kritická kdy¾ $D(x) + D^R(y) + e(x,y) = D(v)$ -% MQ: Toto pozorování mì mate. Co tam má být doopravdy? - -%%%%%% -% -%\s{Definice:} $e \in E(G)$ je most v neorientovaném grafu $G$ právì tehdy, kdy¾ $G-e$ má více komponent ne¾ $G$. -% -%\h{Hledání mostu} -% -%\>{\I Pozorování:} Zpìtná hrana není most. -% -%Jak to poznat o stromové? -% -%\s{Definice:} $\(v) := \min\{\(w) \mid \exists x \in T_v: (x, w) \hbox{ je zpìtná}\}$ -% -%\>{\I Pozorování:} ${u, v}$, $\(u) < \(v)$ není most právì tehdy kdy¾ existuje zpìtná hrana z $T_v$ do $w$ "nad $u$" (t.j. $\(w) < \(u)$) -% -%$\(v) < \(u)$ -% -%$\(s_1) \dots \(sk)$ známe -% -%\>{\I Pozorování:} $\(v) = \min\{\(s_1) \dots \(s_k), in(v), \min\{\(w) \mid (v, w) \hbox{ je zpìtná}\}\}$ -% -%%%%%% - \h{Rozkládání orientovaných grafù na komponenty silné souvislosti} -\s{Definice:} $R$ bude relace na $V(G)$ tak, ¾e $uRv$ znamená, ¾e existuje orientovaná cesta v~$G$ z~$u$ do~$v$ a opaènì. +\s{Definice:} $R$ bude relace na $V(G)$ taková, ¾e $uRv$ právì tehdy, kdy¾ existuje orientovaná cesta v~$G$ z~$u$ do~$v$ a souèasnì z~$v$ do~$u$. % WTF? %\>{\I Pozorování:} Pokud $R$ je ekvivalence a $u...v$ $v...w$ je $u$-$w$ sled $\Rightarrow$ existuje $u$-$w$ cesta. -\s{Definice:} $G$ je silnì souvislý právì tehdy, kdy¾ $\forall (u,v) \in V(G): uRv$. +\s{Definice:} $G$ je {\I silnì souvislý} právì tehdy, kdy¾ $\forall (u,v) \in V(G): uRv$. + +\s{Definice:} {\I Komponenty silné souvislosti} grafu $G$ jsou ekvivalenèní tøídy relace $R$. -\s{Definice:} Komponenty silné souvislosti grafu $G$ jsou tøídy ekvivalence relace $R$. +\s{Poznámka:} Je $R$ vùbec ekvivalence? Ano, zkuste si v definici prohodit $u$ a $v$. -\s{Definice:} Graf komponent $C(G)$ +\s{Definice:} {\I Graf komponent} $C(G)$ $V(C(G))$: Komponenty silné souvislosti grafu $G$ @@ -88,17 +151,22 @@ $(C_1,C_2) \in E(C(G)) \Leftrightarrow \exists v_1 \in C_1, v_2 \in C_2: (v_1, \s{Lemma:} Graf komponent $C(G)$ ka¾dého grafu $G$ je DAG. \proof -Sporem: Nech» $C_1, C_2, \dots C_k$ tvoøí cyklus v~$C(G)$. Potom existují -vrcholy $x_1 \dots x_k \in C_i$ a $y_1 \dots y_k \in C_{i+1}$ takové, ¾e $(x_i, -y_i)$ jsou hrany grafu~$G$. +Sporem: Nech» $C_1, C_2, \dots C_k$ tvoøí cyklus v~$C(G)$. Podle definice grafu +komponent tedy musí existovat vrcholy $x_1 \dots x_k \in C_i$ a $y_1 \dots y_k +\in C_{i+1}$ takové, ¾e $(x_i, y_i)$ jsou hrany grafu~$G$. -V¹echny $C_i$ jsou silnì souvislé, tedy existuje cesta z~$y_{i-1}$ do~$x_i$ -v~$C_i$. Slepením vznikne cyklus v~$G$, co¾ je spor, nebo» v¹echny vrcholy +V¹echny $C_i$ jsou silnì souvislé, tedy existuje cesta z~$y_{i-1} \pmod k$ do~$x_i$ +v~$C_i$. Slepíme nyní v¹echny tyhle cesty a hrany za sebe. +{\catcode`\@\active\let@\rightarrow$$x_1@y_1@\dots@x_2@y_2@\dots@x_3@y_3@\dots\,\dots\,\dots@x_k@y_k@\dots@x_1$$} + +Slepením vznikne cyklus v~$G$, co¾ je spor, nebo» v¹echny vrcholy v~cyklu musí le¾et v jedné komponentì souvislosti. \qed \smallskip +\s{Definice:} {\it Zdroj} v grafu $G$ je takový vrchol, do kterého nevedou ¾ádné hrany + \s{Definice:} {\it Zdrojová komponenta} grafu $G$ je taková komponenta silné souvislosti, která tvoøí zdroj v $C(G)$. @@ -109,7 +177,7 @@ komponenty~$G$. Pustíme-li $\(G)$, pak vrchol s maximálním $\(v)$ le¾í nutnì ve zdrojové komponentì (laskavý ètenáø doká¾e samostatnì). -\s{Tvrzeníèko:} Dále pokud $(C_1, C_2) \in E(C(G))$, pak $$\max_{x \in C_1} \(x) > \max_{x \in C_2} \(x).$$ +\s{Tvrzeníèko:} Pokud $(C_1, C_2) \in E(C(G))$, pak $$\max_{x \in C_1} \(x) > \max_{x \in C_2} \(x).$$ \proof \itemize\ibull @@ -118,84 +186,32 @@ komponent \endlist \qed -\s{Algoritmus:} +Vybereme si tedy vrchol $v_1$ ve zdrojové komponentì grafu $G$ (ten s maximálním $\(v_1)$), spustíme +$\(v)$ v $G^R$ a v¹echny dosa¾ené vrcholy $w$ oznaèkujeme -- $\(w) \la v$. + +Nyní si vybereme vrchol $v_2$ ve zdrojové komponentì neoznaèkované èásti $G'$ +grafu $G$ (ten s maximálním $\(v_2)$) \dots\ a algoritmus analogicky opakujeme, dokud +existují neoznaèkované vrcholy. +\s{Pozorování:} Neoznaèkovaná èást $G'$ grafu $G$ je prázdná, nebo má zdrojovou +komponentu. Kdyby zdrojovou komponentu nemìla, tak nemá zdroj ani $C(G')$, tedy +$C(G')$ buïto obsahuje cyklus (spor s definicí), nebo je prázdný. + +\goodbreak +\s{Algoritmus:} \algo \algin Graf $G$ \:Sestrojíme $G^R$ -\:$Z$ prázdný zásobník, $\(*) \la$ ? +\:$Z \la$ prázdný zásobník, $\(*) \la$ ? \:Spustíme $\(G)$, pøi opu¹tení vrcholu jej vlo¾íme do $Z$. Máme tedy vrcholy v zásobníku setøídìné podle $\(v)$. \:Postupnì pro $v \in Z$: \::Pokud $\(v)=~?$ -\:::pustíme $\(v)$ v $G^R$, nav¹tíveným vrcholùm $w$ nastavíme $\(w) \la v$. +\:::pustíme $\(v)$ v $G^R$ s omezením jen na vrcholy $w$, pro které $\(w) =~?$, v¹em nav¹tíveným vrcholùm $w$ nastavíme $\(w) \la v$. \algout Pro ka¾dý vrchol $v$ vrátíme jeho komponentu $\(v)$. \endalgo -\h{Detekce cyklù v grafu} - -Algoritmus na vypsání {\I v¹ech} cyklù v grafu si neuká¾eme, nebo» tento -problém je tì¾¹í, ne¾ se zdá. Zde probíráme nalezení {\I nìjakého} cyklu v grafu. - -\s{Lemma:} Cyklus je v grafu $G$ právì tehdy, kdy¾ $\(G)$ oznaèí nìjakou -hranu jako zpìtnou. - -\proof Nech» je v grafu $G$ cyklus $v_1,v_2,\dots,v_k,v_1$, nech» $\(G)$ urèí -nìjakou funkci $\$. Nech» je oznaèení vrcholù takové, ¾e $\(v_1)$ je -maximální pøes celý cyklus. Pak jistì $\(v_k) < \(v_1)$. - -Nyní uva¾me poøadí opou¹tìní vrcholù na rùzných typech hran $(x,y)$. Na -stromové, dopøedné a pøíèné hranì platí $\(x) > \(y)$, na zpìtné -$\(x) < \(y)$. Tedy $(v_k,v_1)$ musí být nutnì zpìtná. - -Opaèná implikace je triviální. -\qed - -Dùkaz nám sám dává zpùsob, jak najít cyklus v grafu. - -\s{Algoritmus:} -\algo -\algin Graf $G$ -\:$Z$ budi¾ prázdný zásobník. -\:Spustíme $\(G)$ a pøi nalezení první zpìtné hrany $(u,v)$ zastavíme. -\:Postupnì pro v¹echny otevøené vrcholy $w$ v poøadí, ve kterém by se z~nich DFS vracelo -\::vlo¾íme $w$ na zásobník $Z$ -\::Pokud $w = v$ (nalezli jsme konec zpìtné hrany) -\:::ukonèíme cyklus -\algout Obsah zásobníku $Z$ (nalezený cyklus). -\endalgo - -\h{Hledání mostù v neorientovaném grafu} - -\s{Definice:} Hrana $uv \in E(G)$ je {\I most}, pokud se jejím odebráním -z~grafu $G$ zvý¹í poèet komponent souvislosti tohoto grafu. - -\s{Pozorování:} Hrana, která je v nìjakém cyklu, nemù¾e být mostem. Z cyklu -toti¾ lze libovolnì odebrat jednu hranu a pøesto zùstane souvislý. V¹echny -ostatní hrany naopak mosty jsou. - -Mù¾e být mostem jiná hrana ne¾ stromová? Zpìtné hrany nutnì tvoøí cyklus. -Pøíèné a dopøedné se v neorientovaném DFS neobjeví. - -Hledáme tedy v¹echny stromové hrany, které nejsou v ¾ádném cyklu. Projdeme graf -zase pomocí upraveného DFS. - -Kdy je hrana $uv$ v nìjakém cyklu? Kdy¾ existuje cesta $v\dots w$ (a nebo -$v=w$), zpìtná hrana $wx$ a cesta $x\dots u$ (a nebo $x=u$). - -\smallskip -\s{Algoritmus} bude je¹tì trochu více upravené DFS. Pro ka¾dý vrchol~$v$ si -budeme kromì hloubky je¹tì pamatovat $z(v)$. To bude nejmen¹í \ vrcholu, -do kterého se dá dostat po zpìtných hranách z~vrcholu $v$ nebo podstromu pod ním. - -\algo -\:Vstoupíme do vrcholu $u$ jako DFS. -\:$x \la $~minimum z $\(v)$ pøes v¹echny zpìtné hrany $uv$ -\:$y \la $~minimum ze $z(w)$ pøes v¹echny stromové hrany $uw$ -\:$z(u) \la \min xy$ -\:Pokud $z(u) \ge \(u)$, -\::je jistì mostem hrana, po které jsme vstoupili do $u$. -\endalgo - -\qed +\s{Èasová a pamì»ová slo¾itost} bude $\O(m+n)$, nebo» první DFS má $\O(m+n)$, +ka¾dé dal¹í DFS se omezí jen na svoji komponentu silné souvislosti a souèet +velikostí v¹ech komponent souvislosti je $\O(m+n)$. \bye -- 2.39.2