3.2: グラフの向き付けと探索木  今回の講義目的  無向グラフに H27 グラフ理論無駄なく向きを付ける   強連結な向きアルゴリズム  グラフを効率よく ―第6回― グラフの向き付けと探索どの2頂点も行き来できるように辺に無駄なく向きを付ける(失敗例) 探索する   深さ優先探索 (DFS) 幅優先探索 (BFS) DFSの探索順 1 2 定義(グラフの向き付け)：任意の辺 (u,v) に対して u←v または u→v のいずれかの向きを定義すること．このような有向グラフの道を有向道という．定理3.13 (H.E. ロビンス) 強連結な向き付けが存在する必要十分条件は，グラフ G が連結で橋を含まないことである．定義：どの2頂点に対しても双方向の有向道が存在するとき，その向き付けを強連結という． ※連結：任意の2頂点の間に道がある ※橋：取り除くと連結でなくなるような辺 y x 失敗例 (右から左の頂点に行けない) 強連結な向き付け橋証明（必要条件：強連結な向き付け⇒連結で橋を含まない） G が連結でないときや橋を含むとき，どのように向きを付けても，x から y へ行くことができないか，行くことができても帰ってこられない． 3 4 1 証明（十分条件：⇐）Gが連結で橋を持たないと仮定する．このとき G を次の条件を満たすように分解できる． (1) G = G1∪ G2 ∪ … ∪ Gr かつ (2) Gi+1 は G1∪ G2 ∪ … ∪ Gi と２点を共有する道か，または１点を共有する閉路．(下図) G1 G2 G3 以下同じことを繰り返すことで， G = G1∪ G2 ∪ … ∪ Gr = C1∪ C2 ∪ … ∪ Cr を得ることができる． ... G4 2点を共有する道 1点を共有する閉路 G1 5 証明（つづき）得られた分解 G = C1∪ C2 ∪ … ∪ Cr の各 Ci に対して勝手な１方向へ向き付けをすれば，任意の u,v ∈ V(G) に有向道を構成できる (以下証明)．よって，G は強連結な向き付けを持つ．  証明（つづき：分解の方法） G は連結で橋を持たないので (xとyが2つ以上の道で繋がる)，ある閉路 C1 を持つ．C1を G から取り除いても辺が残るなら，それらをたどると，G は端点を持たないので(橋がないから)，いつかは C1 と合流する．それは道または閉路 C2 となる． (Gが閉路C1のみ)のときはあきらか  r=kのとき正しいと仮定  Ck+1 が C1～Ck と1点で交わる閉路のとき(右図) 任意のx-yのどちらにも有向道がある  Ck+1が道の場合も同様   C1 x C3 C2 y G3 Gr 6 この定理の弱点 r に関する帰納法  r=1 G2  グラフを次々に分解していけばよいが... グラフを閉路(や道)に分解するコストが高いもっと単純な方法がないか？→探索木を使う Ck+1 ひとつひとつ閉路を探すのは大変！！ 7 8 2 もう一つのテーマ(探索木)  DFS (depth first search: 深さ優先探索) 最新の探索点に最も近い未探索の点を次に探索する手法．グラフを効率よく探索  なるべく高速に  なるべくメモリを使わず  すべての頂点を訪れる  出発点 DFS 最も近い未探索点二つの方法  深さ優先探索(DFS)  幅優先探索(BFS) BFS 出発点を指定するか任意に選ぶ DFSの探索木現在点と隣接する未探索の点へ移動する 9 DFSによる探索木（根付き木） 10 木構造に関する定義(再掲) 根葉   葉連結で閉路のないグラフを木という図のような階層構造の木を根付き木という  葉未探索辺を... 削除すると...  根付き木    DFSによって探索した頂点と辺によって構成されるグラフは必ず根付き木となる(探索辺が合流しないため) 根：だれからも指されていない頂点葉：だれも指していない頂点親と子：有向辺の両端先祖と子孫：有向道の両端兄弟：同じ親を持つ頂点根先祖と子孫親と子兄弟葉根付き木の構造 11 12 3 アルゴリズムの動作例強連結な向き付けの効率的手法アルゴリズム3.15 (F.S. ロバーツ) 入力：橋を持たない連結グラフ G 出力：G の強連結な向き付け方法： (1) G の各点にDFSによる探索順位 n(v) を付ける． (DFSによる探索木を T とする) (2) e=(u,v) ∈ T ならば，その辺に探索順位の大きい方へ向きを付ける (3) そうでないなら，逆順に向きを付ける     整数値がDFSの探索順黒矢印が探索木の辺赤矢印が逆辺アルゴリズムの正当性 1 7 C1 2 木に辺を追加するとちょうどひとつの閉路が生まれる  グラフが閉路または道に分解される  定理3.13よりこれは強連結  8 4 5 3 6 C2 9 13 深さ優先探索：その他の応用   有向グラフの頂点 vに順序 L(v) を付ける問題  順序：(u,v)∈E ならば L(u) < L(v)  グラフが閉路を持たないときは必ずこのような順序が存在する 14 トポロジカルソートの例 1 トポロジカルソート C3  3 2 4 トポロジカルソート  1 3 2 下着右グラフは服を着るときの順序関係を表す．例えば，靴下をはく前に靴を履くことはできない．これをトポロジカルソートすると下の順序が得られる．身につけるべき順に並んでいる（すべての辺が左から右へ向いている）靴下ズボン腕時計靴シャツベルトネクタイ上着 4 閉路がある場合はあきらかにトポロジカルソートは存在しない腕時計 15 靴下下着ズボン靴シャツベルトネクタイ上着 16 4 深さ優先探索：応用例2題アルゴリズム 9/14 グラフを深さ優先探索 1. 各頂点に開始時刻と終了 10/13 ズボン時刻を記録する 6/7 2. 頂点を終了時刻の降順でベルト整列する 3. 開始時刻とは，その頂点を最初に訪れた時刻を表す(終了時刻も同様：右図) 17/18 15/16 下着靴下靴  ネクタイ強連結成分分解  部分グラフの任意の2頂点間に道があるとき，その部分グラフを強連結成分という  深さ優先探索後に，そのグラフの逆向きの辺を終了時刻の大きいものからたどれる頂点を同一の強連結成分として取り出す 11/12  1/8 シャツ上着腕時計 2/5 太辺が深さ優先探索した辺 3/4 平面性の判定  グラフが辺を交差しないように平面に描くことができるかを判定できる(下のグラフは平面に描画可能) 3/4 1/10 5/8 2/9 11/18 腕時計靴下下着ズボン靴シャツベルトネクタイ上着 17 もう一つの探索法現在点に隣接するすべてを探索してから現在点を更新 (赤→黄色の順) 15/16 18 幅優先探索の応用 BFS (breasth first search: 幅優先探索) 探索された点に隣接するまだラベル付けされていない点をすべて探索する方法．根を決める 6/7 12/17 13/14  最短経路の発見(右図：重み無しの場合)  二部グラフのテスト  etc... ドイツ都市間の接続を表すグラフフランクフルトからの幅優先探索木 (根からの最短距離) 得られる探索木 19 http://ja.wikipedia.org/ 20 5 二部グラフのテスト   右グラフは同型で二部グラフであるが，ひと目ではわからない簡単なチェック法  あるノードに0を付けて出発点とする  幅優先探索で未探索の点に 0 or 1 を付ける   0 に隣接するなら 1 1 に隣接するなら 0  探索終了後，二部グラフの特性をチェックする二部グラフであるかどうかはひと目ではわからない 21 6