2007/9-dfs/9-dfs.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{9}{Prùchod grafem}{(zapsali T. Hubík, V. Kolomièenko, L. Slinták)}
   4
   5 \h{1. do hloubky (DFS)}
   6
   7 \>$\<in(v)>$, $\<out(v)>$
   8
   9 \>Hrany rozdìlíme do nekolika tøíd
  10 \itemize\ibull
  11 \:{\I stromové} postupují do neoznaèených vrcholù
  12 \:{\I zpìtné} vedou do u¾ oznaèených vrcholù
  13 \:{\I dopøedné} vedou do vrcholù, odkud ji¾ jsme se vrátili
  14 \:{\I pøíèné} pouze zprava doleva
  15 \endlist
  16
  17 \>{\I Pozn.: u neorientovaných grafù mohou být pouze stromové a zpìtné hrany}
  18
  19 {\I Slo¾itost $\O(m+n)$, n ... poèet vrcholù, m ... poèet hran}
  20
  21 \h{2. do ¹íøky (BFS)}
  22 {\I Slo¾itost $\O(m+n)$}
  23
  24 \s{Definice:} {\I Lineární uspoøádání} $<$ vrcholù grafu G je topologické $\Longleftrightarrow \forall (u,v) \in E(G) : u < v$
  25
  26 \>{\I Pozorování: Pro cyklické grafy topologické uspoøádání neexistuje.}
  27
  28 \s{Vìta:} Libovolný acyklický orientovaný graf (DAG) má topologické uspoøádání a lze ho sestrojit v $\O(m+n)$.
  29
  30 \proof
  31 Spustíme DFS, $u < v$ právì tehdy, kdy¾ $\<out(u)> > \<out(v)>$
  32
  33 hrany:
  34 \itemize\ibull
  35 \:stromová - $\<out(u)> > \<out(v)>$
  36 \:zpìtná - existuje cyklus a to je spor
  37 \:dopøedná - $\<out(u)> > \<out(v)>$
  38 \:pøíèná - $\<out(u)> > \<in(u)> > \<out(v)>$
  39 \endlist
  40 \>{\I Dùsledek:} Orientovaný graf $G$ je cyklický $\Longleftrightarrow$ DFS najde zpìtnou hranu, existuje zpìtná hrana $\Rightarrow$ existuje cyklus, neexistuje zpìtná hrana $\Rightarrow$ existuje topologické uspoøádání $\Rightarrow$ neexistuje cyklus.
  41 \qed
  42
  43
  44 \h{Nejdel¹í cesta v DAGU:}
  45
  46 (z $S$ do ka¾dého vrcholu)
  47
  48 \algo
  49 \:Zvolíme topologické uspoøádání na $G$, BÚNO $S$ je minimum.
  50 \:$\forall v: D(v)=-\<inf> ; D(S)=0$
  51 \:Postupnì procházíme vrcholy $v \in V(G)$ v topologickém poøadí a pro $\forall v$ spoèítáme $D(v)$
  52 \:$D(v)=\<max>(D(n))+1$
  53
  54 $u:(u,v) \in E(G)$
  55 \endalgo
  56
  57 \>{\I Pozorování:} Ka¾dý DAG obsahuje {\I zdroj} (vycházejí z nìj cesty) a {\I stok} (cesty do nìj vstupují)
  58
  59 \s{Rozkládání orientovaných grafù na komponenty souvislosti}
  60
  61 \s{Definice:} $R$ bude relace na $V(G)$ tak, ¾e $uRv \Longleftrightarrow$ existuje orientovaná cesta v $G$ z $u$ do $v$ a opaène
  62
  63 \s{Definice:} $G$ je silnì souvislý $\Longleftrightarrow \forall (u,v) \in V(G) : uRv$
  64
  65 \>{\I Pozorování:} $R$ je ekvivalence, $u...v$ $v...w$ je $u$-$w$ sled $\Rightarrow$ existuje $u$-$v$ cesta
  66
  67 {\narrower
  68 \s{Definice:} Komponenty silné souvislosti grafu $G \Longleftrightarrow$ ekvivalence tøídy relace $R$
  69 }
  70
  71 \s{Lemma:} $\forall (G)$ a $\forall (u,v) \in V(G)$: existuje $u$-$v$ sled $\Longleftrightarrow$ existuje $u$-$v$ cesta
  72
  73 \proof
  74 Buï $S$ $u$-$v$ sled, na kterém se opakuje vrchol $z$.
  75 Uva¾me sled $u...z$ $z...v$, co¾ je také $u$-$v$ sled, ale je krat¹í.
  76 Iterujeme $\Rightarrow$ zbude cesta.
  77 \qed
  78
  79 \s{Definice:} Graf komponent $C(G)$
  80
  81 $V(C(G))$: SSK grafu $G$
  82
  83 $(c_1,c_2) \in E(C(G)) \Longleftrightarrow \exists v_1 \in c_1, v_2  \in c_2 : (v_1, v_2) \in E(G) $
  84
  85 \s{Lemma:} $\forall (G) : C(G)$ je DAG.
  86
  87 \proof
  88 obrázkem a sporem, existuje cyklus $c_1, c_2, ..., c_k$ v $C(G)$.
  89 \qed
  90
  91 \h{Algoritmus hladání silnì souvislých komponent grafu v \O(n)}
  92
  93 \>{\I Pozorování 1:} DFS z vrcholu $v$ projde $\{w, \exists v$-$w$ cesta$ \}$.
  94
  95 \>{\I Pozorování 2:} Je-li $C$ stoková komponenta a $v \in  V(C)$, pak DFS z $v$ projde právì $C$.
  96
  97 \>{\I Pozorování 3:} Spustíme-li DFS na celý $G$, pak vchol $v$ s maximální $\<out(v)>$ le¾í ve zdrojové SSK.
  98
  99 \>{\I Pozorování 3*:} Nech» $C_1, C_2$ jsou SSK a $C_1, C_2 \in E(C(G)$, pak $\<max>\{\<out(u)>, u \in V(C_1)\}  > \<max>\{\<out(v)>, v \in V(C_2)\}$.
 100
 101 \>{\I Pozorování 4:} $G$ a $G^R$ mají stejné SSK ( $G^R$ má proti $G$ otoèené hrany ).
 102
 103 \s{Algoritmus:}
 104
 105 \algo
 106 \:Sestrojíme $G^R$ \quad $\O(m+n)$
 107 \:DFS na $G^R \rightarrow \<out(v)>$ \quad $\O(m+n)$
 108 \:$T$ bude uspoøádání vrcholù podle klesajících $\<out(v)>$ \quad $\O(n)$
 109 \:$\forall v \in V(G)$ v poøadí podle $T$ \quad $\O(m+n)$
 110 \:pokud $v$ je¹tì nepatøí do ¾ádné komponenty, tak
 111 \::spustím DFS z $v$ a dosa¾ené vrcholy prohlásím za dal¹í SSK \quad $\O(m+n)$
 112 \endalgo
 113
 114 \s{Vìta:} Ka¾dý orientovaný graf lze rozlo¾it na SSK v èase $\O(m+n)$
 115
 116 \proof
 117 Pozorovani 3*:
 118 \itemize\ibull
 119 \:1. DFS vstoupí nedøíve do $C_1$ : Z $C_2$ vyleze urèitì døív ne¾ z $C_1 \Rightarrow \<out>(C_1) > \<out>(C_2)$.
 120 \:2. nejdøíve do $C_2$: Nejdøív se vrátím z celé $C_2$, a¾ pak nìkdy zase vlezu do $C_1 \Rightarrow \<out>(C_1) > \<out>(C_2)$.
 121 \endlist
 122
 123 \bye
 124