From af0a05cf25bc8a972340b4278eb590dee4cc9d2a Mon Sep 17 00:00:00 2001 From: Jan 'Moskyt' Matejka Date: Mon, 20 Jun 2011 18:58:21 +0200 Subject: [PATCH] 4: opravy prevazne mostu --- 4-dfs/4-dfs.tex | 46 +++++++++++++++++++++++----------------------- 1 file changed, 23 insertions(+), 23 deletions(-) diff --git a/4-dfs/4-dfs.tex b/4-dfs/4-dfs.tex index 6e82533..2ca975e 100644 --- a/4-dfs/4-dfs.tex +++ b/4-dfs/4-dfs.tex @@ -90,10 +90,10 @@ v~cyklu mus souvislosti, která tvoøí zdroj v $C(G)$. \s{Trik:} Uva¾ujme graf $G^R$ (graf $G$, ve kterém otoèíme orientace v¹ech hran). Pokud -$v$~le¾í ve zdrojové komponentì grafu $G$, pak $(v)$ v $G^R$ projde právì +$v$~le¾í ve zdrojové komponentì grafu $G$, pak $\(v)$ v $G^R$ projde právì komponenty~$G$. -Pustíme-li $(G)$, pak vrchol s maximálním $\(v)$ le¾í nutnì ve zdrojové +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).$$ @@ -123,10 +123,10 @@ komponent 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 +\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èí +\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)$. @@ -153,36 +153,36 @@ D \h{Hledání mostù v neorientovaném grafu} -\s{Definice:} Hrana $(u,v) \in E(G)$ je {\I most}, pokud se jejím odebráním +\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. Cyklus je -toti¾ sám o~sobì 2-souvislý. V¹echny ostatní hrany naopak mosty jsou. +\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. -Hledáme tedy v¹echny hrany, které nejsou v ¾ádném cyklu. Projdeme graf zase -pomocí DFS, které bude upravené tak, ¾e ka¾dému vrcholu $v$ pøiøadí -navíc~$h(v)$ -- hloubku ve stromì DFS. +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í. -Kdy je hrana $(u,v)$ v nìjakém cyklu? Kdy¾ existuje cesta $v\dots w$ (a nebo -$v=w$), zpìtná hrana $(w,x)$ a cesta $x\dots u$ (a nebo $x=u$). +Hledáme tedy v¹echny stromové hrany, které nejsou v ¾ádném cyklu. Projdeme graf +zase pomocí upraveného DFS. -\s{Algoritmus} bude je¹tì trochu více upravené DFS. Pro ka¾dý vrchol~$v$ si -budeme kromì hloubky je¹tì pamatovat nejmen¹í hloubku~$z(v)$, do které z~jeho -podstromu vedou zpìtné hrany. +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$). -Jak spoèítáme $z(v)$? +\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, nastavíme $h(u)$. -\:$x \la $~minimum z $h(v)$ pøes v¹echny zpìtné hrany $(u,v)$ -\:$y \la $~minimum ze $z(w)$ pøes v¹echny stromové hrany $(u,w)$ -\:$z(u) = \min (x,y)$ -\:Pokud $z(u) \ge h(u)$, +\: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 -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í. \qed \bye -- 2.39.2