4-dfs/4-dfs.tex

   1 \input ../lecnotes.tex
   2
   3 \prednaska{4}{Aplikace DFS}{}
   4
   5 \h{Nejdel¹í cesta v DAG-u (v grafu bez orientovaných cyklù):}
   6
   7 \s{Definice:} Pro $u,v \in V$ bude $D(u,v)$ délka nejdel¹í cesty z $u$ do $v$.
   8 $D^R(u,v)$ bude délka nejdel¹í cesty v grafu s otoèenými hranami.
   9
  10 Neexistuje-li cesta z $u$ do $v$, nech» $D(u,v) = -\inf$. Zvolme pak $D(u)$
  11 jako nejdel¹í cestu zaèínající v $u$. $$D(u) = \max_{v\in V} D(u,v)$$
  12
  13 \s{Algoritmus:}
  14
  15 \algo
  16 \algin Graf $G$, v nìm vrchol $u$.
  17 \:Zvolíme topologické uspoøádání $w_1 \dots w_n$ na $G$. Nech» $w_k=u$.
  18 \:Pøedpoèítáme si ke ka¾dému vrcholu v¹echny jeho pøedchùdce, tedy mno¾inu
  19 $W_i = \{w_j\mid(w_j,w_i)\in E\}$, v èase i pamìti $\O(n+m)$.
  20 \:Pro v¹echny vrcholy $w_i$ pøed $u$ ($\forall w_i\mid i<k$) nastavíme délku cesty $D(u,w_i)=-\infty$, pro $u$ pak $D(u,u)=0$.
  21 \:Postupnì procházíme vrcholy $w_i \in V(G)$ v topologickém poøadí a pro ka¾dý z nich spoèítáme $D(w_i)$.
  22 $$D(u,w_i)=\max_{w_j \mid (w_j, w_i) \in E} (D(u,w_j)) + e(w_i,w_j)$$
  23 \:Nalezneme maximum z $D(u,w_i)$ pøes v¹echna $i$ a oznaèíme jej $D(u)$.
  24 \algout Vrátime $D(u)$.
  25 \endalgo
  26 \s{Èasová slo¾itost:} Sestrojení topologického uspoøádání a pøedpoèet v $\O(n+m)$. Postupné poèítání $D(u,w)$ také v $\O(n+m)$, celkem $\O(n+m)$.
  27
  28 \s{Definice:} Hrana je kritická právì tehdy, kdy¾ le¾í na nìkteré z nejdel¹ích cest.
  29
  30 %\>{\I Pozorování:} $e = (x,y)$ kritická kdy¾ $D(x) + D^R(y) + e(x,y) = D(v)$
  31 % MQ: Toto pozorování mì mate. Co tam má být doopravdy?
  32
  33 %%%%%%
  34 %
  35 %\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$.
  36 %
  37 %\h{Hledání mostu}
  38 %
  39 %\>{\I Pozorování:} Zpìtná hrana není most.
  40 %
  41 %Jak to poznat o stromové?
  42 %
  43 %\s{Definice:} $\<low>(v) := \min\{\<in>(w) \mid \exists x \in T_v: (x, w) \hbox{ je zpìtná}\}$
  44 %
  45 %\>{\I Pozorování:} ${u, v}$, $\<in>(u) < \<in>(v)$ není most právì tehdy kdy¾ existuje zpìtná hrana z $T_v$ do $w$ "nad $u$" (t.j. $\<in>(w) < \<in>(u)$)
  46 %
  47 %$\<low>(v) < \<in>(u)$
  48 %
  49 %$\<low>(s_1) \dots \<low>(sk)$ známe
  50 %
  51 %\>{\I Pozorování:} $\<low>(v) = \min\{\<low>(s_1) \dots \<low>(s_k), in(v), \min\{\<in>(w) \mid (v, w) \hbox{ je zpìtná}\}\}$
  52 %
  53 %%%%%%
  54
  55 \h{Rozkládání orientovaných grafù na komponenty souvislosti}
  56
  57 \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ì.
  58
  59 % WTF?
  60 %\>{\I Pozorování:} Pokud $R$ je ekvivalence a $u...v$ $v...w$ je $u$-$w$ sled $\Rightarrow$ existuje $u$-$w$ cesta.
  61
  62 \s{Definice:} $G$ je silnì souvislý právì tehdy, kdy¾ $\forall (u,v) \in V(G): uRv$.
  63
  64 \s{Definice:} Komponenty silné souvislosti grafu $G$ jsou tøídy ekvivalence relace $R$.
  65
  66 \s{Definice:} Graf komponent $C(G)$
  67
  68 $V(C(G))$: Komponenty (silne souvislého) grafu $G$
  69
  70 $(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)$
  71
  72 \smallskip
  73
  74 \s{Lemma:} Graf komponent $C(G)$ ka¾dého grafu $G$ je DAG.
  75
  76 \proof
  77 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$. V¹echny $C_i$ jsou silne souvislé, teda existuje cesta z~$y_{i-1}$ do~$x_i$ v~$C_i$. Slepením vznikne cyklus v~$G$, co¾ je spor.
  78 \qed
  79
  80 \smallskip
  81
  82 \s{Trik:}
  83
  84 1. Uva¾ujme graf $G^R$ ($G$ s hranami opaène)
  85
  86 ~~~Pokud $v$ le¾í ve zdrojové komponente grafu $G$, pak DFS(v) v $G^R$ projde právì komponenty G.
  87
  88 2. Vrchol s maximálním $\<out>(v)$ le¾í ve zdrojové komponente.
  89
  90 2*. Pokud $(C_1, C_2) \in E(C(G))$, pak $\max_{x \in C_1} \<out>(x) > \max_{x \in C_2} \<out>(x)$.
  91
  92 \proof
  93 2*:
  94 \itemize\ibull
  95 \:a.) 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)$.
  96 \:b.) 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)$.
  97 \endlist
  98 \qed
  99
 100 \s{Algoritmus:}
 101
 102 \algo
 103 \algin Graf $G$
 104 \:Sestrojíme $G^R$
 105 \:$S \in \emptyset$ seznam, $\<komp>(*) \Rightarrow$ ?
 106 \:Spustíme $\<DFS>(G)$, pøi opu¹tení vrcholu ho pøidáme na zaèátek $S$.
 107 \:Postupòe pro $v \in S$:
 108 \::Pokud $\<komp>(v)=~?$
 109 \:::pustíme $\<DFS>(v)$ v $G^R$, nav¹tíveným vrcholom $w$ nastavíme $\<komp>(w) \Rightarrow v$.
 110 \algout Pro ka¾dý vrchol $v$, jeho komponentu $\<komp>(v)$.
 111 \endalgo
 112
 113 \bye