算法数理工学 第8回 定兼　邦彦.

Presentation on theme: "算法数理工学 第8回 定兼　邦彦."— Presentation transcript:

1 算法数理工学 第8回 定兼　邦彦

2 深さ優先探索，幅優先探索 木やグラフの探索法 深さ優先探索 (depth-first search, DFS)
行き止まりになるまで先に進む 幅優先探索 (breadth-first search, BFS) 全体を同時に探索する DFSはスタック(再帰)，BFSはキューで実現できる 1 3 4 2 5 6 1 4 5 2 3 6 DFS BFS

3 DFS(G) for each u  V[G] color[u]  白 [u]  NIL time  0 if color[u] = 白 DFS-Visit(u) DFS-Visit(u) color[u]  灰 time  time + 1 d[u]  time for each v  Adj[u] if color[v] = 白 [v]  u DFS-Visit(v) color[u]  黒 f[u]  time

4 白：未訪問 灰：探索中 黒：探索終了 u v w 1/ x y z

5 u v w 1/ 2/ x y z

6 u v w 1/ 2/ 3/ x y z

7 u v w 1/ 2/ 4/ 3/ x y z

8 辺 (x, v) をたどる v は既に訪問しているので行かない u v w 1/ 2/ 4/ 3/ x y z

9 白：未訪問 灰：探索中 黒：探索終了 u v w 1/ 2/ 4/5 3/ x y z

10 u v w 1/ 2/ 4/5 3/6 x y z

11 u v w 1/ 2/7 4/5 3/6 x y z

12 辺 (u, x) をたどる x は既に訪問しているので行かない u v w 1/ 2/7 4/5 3/6 x y z

13 u v w 1/8 2/7 4/5 3/6 x y z

14 u v w 1/8 2/7 9/ 4/5 3/6 x y z

15 u v w 1/8 2/7 9/ 4/5 3/6 x y z

16 u v w 1/8 2/7 9/ 4/5 3/6 10/ x y z

17 u v w 1/8 2/7 9/ 4/5 3/6 10/ x y z

18 u v w 1/8 2/7 9/ 4/5 3/6 10/11 x y z

19 u v w 1/8 2/7 9/12 4/5 3/6 10/11 x y z

20 辺 (u, v) をたどったら，v の親を u にする ([v] = u) グラフ G = (V, E) を次のように定義する
E = {([v], v)  E | v  V かつ [v]  NIL} G は深さ優先探索森 (depth-first forest) 連結ならば深さ優先探索木 (depth-first tree) 各点は探索前は白,探索中は灰,探索終了後は黒 各点 v は2つのタイムスタンプを持つ d[v] は v を最初に発見した (灰色にした) 時刻 f[v] は v の隣接リストを調べ終わった (黒にした) 時刻 タイムスタンプは 1 から 2n の整数 全ての u に対し d[u] < f[u] DFSの実行時間は (n+m)

21 定理 (括弧付け定理): グラフ G に対する任意の深さ優先探索を考える．任意の2つの頂点 u, v に対し，以下の3つの条件の中の1つだけが成立する．
区間 [d[u], f[u]] と区間 [d[v], f[v]] には共通部分が無く，深さ優先森において u と v はどちらも他方の子孫ではない． 区間 [d[u], f[u]] は区間 [d[v], f[v]] に完全に含まれ， u が v の子孫となる深さ優先探索木が存在する 区間 [d[v], f[v]] は区間 [d[u], f[u]] に完全に含まれ， v が u の子孫となる深さ優先探索木が存在する 注：2つの区間が部分的に重なることは無い

22 証明： まず d[u] < d[v] の場合を考える d[v] < f[u] のとき
u がまだ灰色のときに v が発見されている．つまり v は u の子孫． v は u よりも後に発見されたので，u の探索が終わる前に v の探索は終わる．つまり f[v] < f[u]． このとき区間 [d[v], f[v]] は区間 [d[u], f[u]]に含まれる． f[u] < d[v] のとき d[u] < f[u] < d[v] < f[v] なので区間に共通部分は無い． つまり一方が探索中に他方が発見されない． よってどちらも他方の子孫では無い d[v] < d[u] の場合も同様に証明できる．

23 系：有向または無向グラフに対する深さ優先探索森において頂点 v が 頂点 u ( v) の子孫であるための必要十分条件は d[u] < d[v] < f[v] < f[u]
定理 (白頂点経路定理)： グラフ G の深さ優先探 索森において，頂点 v が 頂点 u の子孫であるため の必要十分条件は，探索が u を発見する時刻 d[u] に u から v に至る白頂点だけからなるパスが 存在することである． 証明：⇒) v が u の子孫であると仮定する．uv間のパス上の任意の頂点を w とする．w は u の子孫なので，d[u] < d[w]．つまり時刻 d[u] では w は白．

24 ←) 時刻 d[u] に u から v に至る白頂点だけからなるパスが存在するが，深さ優先探索木において v が u の子孫にならないと仮定する．一般性を失うことなく，このパス上の v 以外の全ての頂点は u の子孫になると仮定できる． このパス上で v の直前の点を w とする． w は u の子孫 (uを含む) なので f[w]  f[u]. v の発見は u の後で，w の終了の前なので， d[u] < d[v] < f[w]  f[u]. 区間は部分的には重ならないので f[v] < f[u]. つまり v は u の子孫．

25 y z s t 3/6 2/9 1/10 11/16 4/5 7/8 12/13 14/15 x w v u s t z v u y w x (s (z (y (x x) y) (w w) z) s) (t (v v) (u u) t)

26 辺の分類 グラフ G の深さ優先探索森 G を1つ固定する． G の辺を4種類に分類する tree edge (木辺)
back edge (後退辺) 辺 (u, v) で，u と v がある深さ優先探索木の頂点とその先祖の場合．セルフループも後退辺とみなす． forward edge (前進辺) 辺 (u, v) で，木辺でなく，u と v がある深さ優先探索木の頂点とその子孫の場合． cross edge (横断辺) 上の3つ以外

27 定理: 無向グラフ G を深さ優先探索するとき，G の任 意の辺は木辺または後退辺である． 証明: (u, v) を G の任意の辺とし，一般性を失うこと なく d[u] < d[v] と仮定する． v は u の隣接リストに含まれるので，u に対する処理 が終わる前に v に対する処理が終わる． 辺 (u, v) が最初に u から v に向かって探索されたな ら，v はその時点では白である．すると (u, v) は木辺. 辺 (u, v) が最初に v から u に向かって探索されたな ら，u はその時点では灰である．すると (u, v) は 後退辺.

28 定理: ・辺 (u,v) が木辺または前進辺 ⇔ d[u] < d[v] < f[v] < f[u] ・辺 (u,v) が後退辺 ⇔ d[v] < d[u] < f[u] < f[v] ・辺 (u,v) が横断辺 ⇔ d[v] < f[v] < d[u] < f[u]

29 トポロジカルソート 入力：閉路のない有向グラフ G = (V, E)
出力： Gの全頂点の線形順序で， G が辺 (u, v) を含む ⇔ この線形順序で u が v より先に現れる 注：グラフに閉路があればそのような線形順序は存在しない 半順序しか定義されていない集合に，それと矛盾しない全順序を1つ与えることに相当する． (n+m) 時間で求まる． 閉路を持たない有向グラフは DAG (directed acyclic graph) と呼ばれる

30 全ての有向辺が左から右の向きになっている 注：トポロジカルソートは1通りでは無い
socks 17/18 11/16 undershorts shoes 13/14 12/15 pants shirt 1/8 watch 9/10 6/7 belt tie 2/5 jacket 3/4 socks undershorts pants shoes watch shirt belt tie jacket 17/18 11/16 12/15 13/14 9/10 1/8 6/7 2/5 3/4 全ての有向辺が左から右の向きになっている 注：トポロジカルソートは1通りでは無い

31 TOPOLOGICAL-SORT(G) L   (空リスト) for each u  V[G] color[u]  白 if color[u] = 白 Visit(u) Visit(u) if color[u] = 灰 stop (DAGでは無い) if color[u] = 黒 return color[u]  灰 for each v  Adj[u] Visit(v) color[u]  黒 L の先頭に u を入れる 時間計算量: (n+m)

32 補題1: 有向グラフ G に閉路が存在しない ⇔ G を深さ優先探索した時に後退辺を生成しない 証明: →) 後退辺 (u, v) が存在すると仮定する． つまり深さ優先探索木において v は u の祖先． v から u のパスに後退辺(u, v)を加えると閉路になる. ←) G が閉路 c を含むと仮定する．c の中で最初に 訪れられる点を v とし，c において v に入る辺を(u, v) とする．時刻 d[v] では，c 内の頂点は全て白である． よって v から u まで白頂点のみからなるパスが存在 するため，vは uの先祖であり，(u, v)は後退辺となる.

33 補題: トポロジカルソートのアルゴリズム実行時に 辺 (u, v) が探索されたとする．グラフに閉路が無い ⇔ v は灰色ではない． (つまり，v が灰色なら解は存在しない) 証明: v が灰色なら，v は u の先祖であり， (u, v) が 後退辺となる．前の補題からグラフは閉路を持つ． グラフに閉路があるなら，後退辺 (u, v) が存在し， v は灰色である．

34 定理: TOPOLOGICAL-SORT(G)は有向グラフGが 閉路を持たないなら G をトポロジカルソートし，閉路 を持つならその1つを発見する． 証明: グラフが閉路を持つなら後退辺 (u, v) が存在 し，v の色は灰となる．アルゴリズムは全ての辺を 調べるので，閉路があるなら必ず発見する． 以下ではグラフが閉路を持たない場合を考える． 頂点はその探索の終了時にLの先頭に挿入される. つまり L には頂点は終了時刻 f[] の降順に入って いる．よって，G の中に辺 (u, v) があるときに f[v] < f[u] となっていることを示せばいい．

35 アルゴリズムが辺 (u, v) を探索する時点を考える． v の色は白か黒である．v が白なら v は u の子孫に なり， f[v] < f[u] が成立する． v が黒なら v の処理 は既に終了しているので，f[v] は既に決定されてい る．u は探索中なので f[u] は未決定である． よって f[v] < f[u] となる．

36 強連結成分分解 定義: 有向グラフ G = (V, E) の強連結成分 (strongly connected component) とは，次の条件を満たす 頂点の集合 C  V で極大なものと定義する． C の全ての頂点対に対して u v かつ v u (u v はuからvへ有向パスが存在することを表す．) Cが極大とは，C  C’, C  C’ となる強連結成分 C’ は無いという意味 つまり，u と v は互いに到達可能である．

37 13/14 11/16 1/10 12/15 3/4 4つの強連結成分 (SCC) を持つ 注： 各SCCは1つの閉路とは限らない
a b c d 13/14 11/16 1/10 8/9 12/15 3/4 2/7 5/6 e f g h 4つの強連結成分 (SCC) を持つ 注： 各SCCは1つの閉路とは限らない 1点でもSCCになる

38 各強連結成分を1点に縮約すると，DAGになる
b c d 13/14 11/16 1/10 8/9 12/15 3/4 2/7 5/6 e f g h abe cd h fg 各強連結成分を1点に縮約すると，DAGになる

39 定義: グラフ G = (V, E) の転置とは，次のように
定義されるグラフ GT = (V, ET) である． ET = {(v, u) | (u, v)  E} GT の隣接行列は，G の隣接行列の転置になる． GT は線形時間 (n+m) で求まる． G の各頂点 u に対し，その隣接点 v  Adj[u] を 　列挙し，辺 (v, u) を GT の v の隣接リストに挿入

40 SCC(G) // Strongly-Connected-Components
DFS(G) を呼び出し，各頂点 u に対して終了時刻 f[u] を計算する GT を計算する DFS(GT) を呼び出す．ただし 1. で計算した f[u] の降順で頂点を探索する 3. で生成した深さ優先探索森の各木の頂点集合を1つの強連結成分として出力する (n+m) 時間

41 補題: 有向グラフ G=(V, E) の異なる2つの強連結 成分を C と C’, u, v  C, u’, v’  C’ とする．
G に経路 u u’ が存在するとき，G には経路 v’ v は存在しない. 証明: G に経路 v’ v が存在すると仮定すると， 経路 u u’ v’ と v’ v u が存在する． 従って u と u’ は互いに到達可能であり，C と C’ が 異なる強連結成分であることに矛盾する． v v’ C’ C u’ u

42 定義: d(U) = minu  U {d[u]} f(U) = maxu  U {f[u]}
つまり， d(U) と f(U) は U の頂点の発見時刻と終了 時刻の中で最も早い時刻と最も遅い終了時刻． 補題: 有向グラフ G=(V, E) の異なる2つの強連結 成分を C と C’ とする. u  C, v  C’ である辺 (u, v) が存在するなら，f(C) > f(C’) である. C’ C v u

43 時刻 d[x] では C と C’ の点は全て白で，x から u に 至る白頂点だけからなるパスが G に存在する．
証明: d(C) < d(C’) の場合 C の中で最初に発見される点を x とする． 時刻 d[x] では C と C’ の点は全て白で，x から u に 至る白頂点だけからなるパスが G に存在する． (u, v)  E なので，時刻 d[x] では x から任意の頂点 w  C’ に至る白頂点だけからなるパスが G に存在 する．つまり x u  v w である．白頂点経路 定理より C’ の全頂点はDFS木で x の子孫となり， f[x] = f(C) > f(C’). x w C’ C v u

44 d(C) > d(C’) の場合. C’ の中で最初に発見される 点を y とする．時刻 d[y] では C’ の全頂点は白で，
DFS木において y の子孫となり，f[y] = f(C’) となる． 時刻 d[y] では C の全頂点は白である．C から C’ に 辺 (u, v) が存在するので， C’ から C にはパスは 存在しない． y C’ C v u

45 C の任意の頂点は y から到達不可能なので， 時刻 f[y] には C の全頂点はまだ白のままである．
従って，任意の頂点 w  C に対して f[w] > f[y]， すなわち f(C) > f(C’) が成立する． 系1: C と C’ を有向グラフ G=(V, E) の異なる2つの 強連結成分とする． u  C と v  C’ の間に 辺 (u, v)  ET があるとき，f(C) < f(C’) である． w y C’ C v u

46 定理: アルゴリズム SCC は有向グラフ G の強連結 成分を正しく求める． 証明: 帰納法で示す．アルゴリズムの3行目で求めた 最初の k 個の木が強連結成分のときに，k+1 個目も 強連結成分であることを示す．k=0のときは成り立つ. (k+1) 番目の木の根を u とし，u の属する強連結成分 を C とする．この後で訪問する C 以外の任意の強連 結成分 C’ に対して f[u] = f(C) > f(C’) が成立する． 帰納法の仮定(最初の k 個の木が強連結成分)から, C の一部の頂点が既に訪れられていることはない．

47 白頂点経路定理より，u からの深さ優先探索木に おいて C の他のすべての頂点は u の子孫になる． さらに，帰納法の仮定と系1から，GTの C から出る 任意の辺は既に訪問された強連結成分への辺で ある．従って，C 以外の任意の強連結成分に属する どの頂点も，u からの深さ優先探索によって u の 子孫になることはない．よって，u を根とする深さ優先 探索木の全頂点は1つの強連結成分に対応する．

48 最大流問題とフロー増加法 各枝に容量が与えられたネットワーク G = (V,E) において，ソース s  V からシンク t  V に向かってできるだけ多くのものを送ることを考える 枝 (i,j) 上の流れの大きさを xij，枝 (i,j) の容量，つまり流れ xij の上限値を uij，ソースからシンクへの総流量を f とすると，問題は次のような線形計画問題として定式化できる 1 2 3 4 5 8 ソース シンク

49 流れ保存則 容量制約条件 制約条件1: s からの正味の流出量が f 制約条件3: t への正味の流入量が f
制約条件： 流れ保存則 制約条件1: s からの正味の流出量が f 制約条件3: t への正味の流入量が f 制約条件2: s と t 以外の節点では流入量 = 流出量 容量制約条件 制約条件4: 各枝の流量が非負かつ枝の容量以下

50 流れ保存則と容量制約条件を満たす x = (xij) を フローと呼びそれに対する f をフローの流量と呼ぶ
最大流問題は，流量が最大になるフローを求める問題 最大流問題は線形計画問題なので単体法などで解くことができるが，ここではネットワーク問題の特性を利用したアルゴリズムを考える 1 2 3 4 5 8 ソース シンク

51 残余容量と残余ネットワーク ネットワークにおいて，任意の2節点 i, j  V の間に枝(i,j)と(j,i)の両方が存在することはないと仮定 あるフロー x = (xij) が与えられているとする．ネットワーク G = (V,E) の各枝 (i,j)  E を容量 を持つ枝 (i,j) と，容量 を持つ枝 (j,i) で 置き換える なら枝 (j,i) のみ， なら枝 (i,j) のみ i j

52 をフロー x に対する枝 (i,j) の残余容量という
ネットワーク G の各枝 (i,j) を上のように置き換えたネットワークを，フロー x に対する残余ネットワークと言い，Gx = (V,Ex) と書く 元のネットワーク G 1 2 3 4 5 8 残余ネットワーク Gx 1 2 3 4 5 6 フロー x 1 2 3 4 5 (3) (4) (2) (1) (0) (6)

53 そのような路を，(現在のフロー x に対する) フロー増加路と呼ぶ
残余ネットワークにおいて，ソースからシンクへの路が存在すれば，その路に沿ってフローを追加することによって，元のネットワーク上での流量 f を 増やせることがわかる そのような路を，(現在のフロー x に対する) フロー増加路と呼ぶ フロー増加路に沿って追加できるフローの量は，その路に含まれる枝の残余容量の最小値に等しい 残余ネットワーク Gx 1 2 3 4 5 6

54 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 (1) (3) (0) (2) (1) (4) (6) (4) (2) (3)
フロー x 1 2 3 4 5 (3) (4) (2) (1) (0) (6) 新しいフロー x 1 2 3 4 5 (4) (3) (1) (2) (6) 残余ネットワーク Gx フロー増加路 (流量1) 1 2 3 4 5 6

55 フロー増加法 (Ford-Fulkerson法)
最大流を求めるアルゴリズム (正当性の証明は後) (0) 適当な初期フロー x を求める 例えば，全ての枝 (i,j) に対し xij = 0 とする 残余ネットワーク Gx においてソースからシンクへの路 (フロー増加路) を見つける 存在しなければ計算終了 フロー増加路に沿って可能な限りフローを追加し，新しいフロー x を得る．ステップ(1)に戻る

56 初期フロー 残余ネットワーク 1 2 3 4 5 (0) 1 2 4 5 3 3 5 1 5 4 3 8 フロー 残余ネットワーク 1 2 3 4 5 (0) (4) 1 2 4 5 3 3 5 1 4 5 4 3 4

57 フロー 残余ネットワーク 1 2 3 4 5 (3) (4) (0) (7) 1 2 4 2 3 3 3 5 1 1 5 4 3 7 フロー 残余ネットワーク 1 2 3 4 5 (4) (3) (1) (0) (7) 1 2 4 1 2 3 5 4 1 1 1 5 4 3 7 フロー増加路が存在しないので終了 フローの流量は 8

58 フロー増加法の正当性と 最大流最小カット定理
枝の容量が全て整数なら，初期フローを整数値としてフロー増加法を用いると，ソースからシンクへの流量は1回の反復で少なくとも1は増える よって有限回の反復の後にアルゴリズムは終了 終了した時点でのフローが最大流になっていることを示す

59 頂点集合V をソースs を含む集合Sとシンクt を含む集合T に分割したものをカットと言い，(S,T) と表す
任意のカット (S,T) に対して，S の節点を始点とし， T の節点を終点とする枝を (i,j)  (S,T)，逆に， T の節点を始点とし，S の節点を終点とする枝を (j,i)  (T,S) と書く 全ての枝 (i,j)  (S,T) の容量 uij の合計を カット (S,T) の容量と呼び，C(S,T) で表す．つまり

60 x を任意のフロー，f をその流量，(S,T) を任意のカットとする
が成立する 全ての枝 (i,j) E に対して 0  xij  uij であるから， カット容量の定義より，f  C(S,T) を得る

61 フロー増加法の計算が終了した時点で得られているフローを x*，その流量を f * とする
残余ネットワークでs から到達できる点の集合をS*, その補集合を T* とする s  S* かつ t  T* より，(S*,T*) はカットとなる 残余ネットワークの定義より

62 従って， 任意のフローに対して f  C(S,T)が成り立つので， 上の式は x* が実行可能な全てのフローの中で 最大流量を与えるものであり，同時に，(S*,T*) が 全てのカットの中で最小の容量をもつものであることを示している (最大流最小カットの定理) 以上より，フロー増加法が終了したときのフローは最大流になっている

63 フロー増加法の計算量とその改良 容量が整数値のとき，フロー増加法では1回の反復で少なくとも1単位の流量が追加される
　⇒ 全体の反復回数は最大流量の値を越えない 枝の容量の最大値を U = max{uij| (i,j)  E} とすると，最大流量の上限は mU 1つのフロー増加路を見つける計算量は O(m) 全体の計算量は O(m2U) 計算量に U が現れるので，理論的には多項式時間アルゴリズムとは言えない

64 Edmonds-Karpアルゴリズム フロー増加法において，フロー増加路を求める際に辺数最小のものを求める
幅優先探索で路を求めればいい 反復回数が mn/2 以下になる (後述) 全体の時間計算量は O(m2n)

65 i 回目の反復後のフローを fi とする i+1 回目の反復では，残余ネットワーク で辺数 最小のフロー増加路 Pi を求め，フロー fi+1を流す 補題：フローの系列 f1, f2,... に対し (a) 全ての k で |E(Pk)|  |E(Pk+1)| (b) Pk  Pl が逆辺対を持つような全ての k < l に対して， |E(Pk)| + 2  |E(Pl)|

66 証明：(a) Pk  Pk+1 から逆辺対を全て除去した グラフを G1 とする Pk と Pk+1 の両方に現れる辺は多重辺とする
G1 には2つの辺素な s-t パス Q1, Q2 が存在する の任意の辺はPk の辺の逆辺となる の辺は Pk にそってフローを流したときにできたので，それは流量が 0 のところにフロー Pk を流したあとの残余ネットワークの辺であるから s t Pk Pk+1 s t Q1 Q2 G1

67 G1 の枝は Pk  Pk+1 に含まれるが，後者の枝の 中で の枝は Pk の逆辺なので 削除されている．よって
Q1, Q2 の枝は G1 に含まれるので，Q1, Q2 は での増加路である Pk は辺数最小の増加路なので，|E(Pk)|  |E(Q1)| かつ |E(Pk)|  |E(Q2)| 以上より |E(Pk)|  |E(Pk+1)| (Q1とQ2はG1の辺素パス) (G1は逆辺を削除)

68 (b) の証明： k < i < l である全ての i に対しPi  Pl が逆辺を持たないようなk, l に対して証明できれば, (a) より全ての k < l に対しても成り立つ Pk  Pl から逆辺対を全て除去したグラフを G1 とする であり， の任意の辺は Pk, Pk+1,...,Pl-1 の いずれかに含まれる辺の逆辺である よって，Pl の辺で Pk の逆辺でないものは， の辺か Pk+1,...,Pl-1 の辺の逆辺である k と l の定め方より，Pl は Pk+1,...,Pl-1 の辺の逆辺を持たない．

69 よって，Pl の辺で Pk の逆辺でないものは の辺となり， が得られる
G1 には2つの辺素な s-t パス Q1, Q2 が存在し， それらは での増加路である Pk は辺数最小の増加路なので，|E(Pk)|  |E(Q1)| かつ |E(Pk)|  |E(Q2)| 　 (少なくとも2辺を除去しているので) より，命題が成り立つ

70 定理： 辺数 m, 点数 n のネットワークに対して， Edmonds-Karpアルゴリズムは辺の容量に関わらず，高々 mn/2 回の反復で終了する
証明：アルゴリズムの実行中に選ばれた増加路を P1, P2,... とする 増加路で可能な限りフローを追加するので，各増加路には残余ネットワークでの容量いっぱいまで流す枝が存在する．それをボトルネック辺と呼ぶ 任意の辺 e に対して，e をボトルネック辺にもつ増加パスを とする と の間に，e の逆辺を含む増加路 が存在する (ij < k < ij+1)

71 補題 (b) より，全ての j に対し e が端点として s と t を含まなければ，全ての j で となり，e をボトルネック辺としてもつ増加路は高々 n/4 個 e が端点として s と t のいずれかを含むときは， e またはその逆辺をボトルネック辺として持つ増加路は高々1つ 任意の増加路は G の辺かその逆辺を少なくとも 1本含むので，高々 2m  n/4 = mn/2 個の増加路しか選ばれない