離散数学 11. その他のアルゴリズム五島 DATE : 離散数学グラフに関するその他のアルゴリズム  最大流問題  平面グラフ  同形性  グラフのマッチング  etc. 離散数学最大流問題離散数学最大流問題  最大流問題 (maximum flow problem)  ネットワーク・フロー問題 (network flow problem)  辺にふった容量以下の流量  始点から終点に流せる最大の流量は？ 5/5 4/4 9 6/8 1/2 0/3 1/1 5/5 3/3 4/4 9 離散数学 Ford-Fulkerson のアルゴリズム  アイディア  始点から終点に至る経路の，どの辺にも余裕がある  ⇒ その経路の流量を増やす  これを繰り返す  鍵：  このような経路をいかに組織的に探すか？離散数学他のアルゴリズム  線形計画法 (linear programming)  Edmonds-Karp のアルゴリズム  Ford-Fulkerson の特殊ケース  Dinitz のアルゴリズム  動的木を使った Dinitz のアルゴリズム  汎用プッシュ再ラベル法  FIFO式頂点選択規則付きプッシュ再ラベル法  動的木を使ったプッシュ再ラベル法離散数学平面性の問題離散数学平面グラフ  平面グラフ (planar graph)  辺を交差させずに平面に描けるグラフ離散数学平面グラフ（別の定義）  平面グラフ (plane graph)：辺を交差させずに平面に描いたグラフ  平面的グラフ (planar graph)：辺を交差させずに平面に描けるグラフ  平面描画 (planar drawing)：辺を交差させずに平面に描画したもの離散数学平面性の判定  IC，LSI の配線  層内は平面でなければならない  実際には，多層で via があるので…  深さ優先探索を用いるアルゴリズムがある  O(m + n) で，すなわち，効率よく解ける！離散数学非平面グラフ  平面グラフ ⇔ 以下の2つに縮約可能な部分グラフを含まない離散数学同形性の判定離散数学同形性 (isomorphism)  2つのグラフが同形  頂点を1対1に対応させた時，辺の接続関係が同じになる離散数学  原理的には，全ての組み合わせについて辺が一致するか検査  ⇒ O(n!)  実際には，全ての組み合わせを試す必要はない  頂点の入出力の数が違うとか，  ⇒ O(an), (a > 1)  この問題を解くのに，指数関数的な計算量が必要かどうかは分かっていない！  必要としないアルゴリズムは見つかっていない（見つかる見込みは薄い？）  必要と証明されてもいない離散数学グラフのマッチング離散数学 2部グラフ  2部グラフ (bi-partite graph)  2つの「部」の間だけに辺がある  それぞれの「部」の中には辺がない離散数学グラフのマッチング  グラフのマッチング  辺で結ばれた2つの頂点を「組」にする  各頂点は，1つの組にしか属さない  応用：  人と仕事  学生と研究室離散数学アルゴリズム  目標：  組に属さない頂点数を最小にする  O(m n) のアルゴリズムが知られている  辺の重みの和を最大にする  etc