離散数学 11. その他のアルゴリズム 五島.

Presentation on theme: "離散数学 11. その他のアルゴリズム 五島."— Presentation transcript:

1 離散数学 11. その他のアルゴリズム 五島

2 離散数学 グラフに関するその他のアルゴリズム 最大流問題 平面グラフ 同形性 グラフのマッチング etc.

3 離散数学 最大流問題

4 最大流問題 最大流問題 (maximum flow problem) ネットワーク・フロー問題 (network flow problem)
離散数学 最大流問題 最大流問題 (maximum flow problem) ネットワーク・フロー問題 (network flow problem) 辺にふった容量以下の流量 始点から終点に流せる最大の流量は？ 5/5 4/4 6/8 9 1/2 9 0/3 1/1 5/5 3/3 4/4

5 Ford-Fulkerson のアルゴリズム
離散数学 Ford-Fulkerson のアルゴリズム アイディア 始点から終点に至る経路の，どの辺にも余裕がある ⇒ その経路の流量を増やす これを繰り返す 鍵： このような経路をいかに組織的に探すか？

6 他のアルゴリズム 線形計画法 (linear programming) Edmonds-Karp のアルゴリズム
離散数学 他のアルゴリズム 線形計画法 (linear programming) Edmonds-Karp のアルゴリズム Ford-Fulkerson の特殊ケース Dinitz のアルゴリズム 動的木を使った Dinitz のアルゴリズム 汎用プッシュ再ラベル法 FIFO式頂点選択規則付きプッシュ再ラベル法 動的木を使ったプッシュ再ラベル法

7 離散数学 平面性の問題

8 離散数学 平面グラフ 平面グラフ (planar graph) 辺を交差させずに平面に描けるグラフ

9 平面グラフ（別の定義） 平面グラフ (plane graph)： 辺を交差させずに平面に描いたグラフ
離散数学 平面グラフ（別の定義） 平面グラフ (plane graph)： 辺を交差させずに平面に描いたグラフ 平面的グラフ (planar graph)： 辺を交差させずに平面に描けるグラフ 平面描画 (planar drawing)： 辺を交差させずに平面に描画したもの

10 平面性の判定 IC，LSI の配線 層内は平面でなければならない 実際には，多層で via があるので…
離散数学 平面性の判定 IC，LSI の配線 層内は平面でなければならない 実際には，多層で via があるので… 深さ優先探索を用いるアルゴリズムがある O(m + n) で，すなわち，効率よく解ける！

11 離散数学 非平面グラフ 平面グラフ ⇔ 以下の2つに縮約可能な部分グラフを含まない

12 離散数学 同形性の判定

13 離散数学 同形性 (isomorphism) 2つのグラフが 同形 頂点を1対1に対応させた時，辺の接続関係が同じになる

14 原理的には，全ての組み合わせについて辺が一致するか検査 ⇒ O(n!) 実際には，全ての組み合わせを試す必要はない
離散数学 原理的には，全ての組み合わせについて辺が一致するか検査 ⇒ O(n!) 実際には，全ての組み合わせを試す必要はない 頂点の入出力の数が違うとか， ⇒ O(an), (a > 1) この問題を解くのに，指数関数的な計算量が必要かどうかは分かっていない！ 必要としないアルゴリズムは見つかっていない（見つかる見込みは薄い？） 必要と証明されてもいない

15 離散数学 グラフのマッチング

16 離散数学 2部グラフ 2部グラフ (bi-partite graph) 2つの「部」の間だけに辺がある それぞれの「部」の中には辺がない

17 グラフのマッチング グラフのマッチング 辺で結ばれた2つの頂点を「組」にする 各頂点は，1つの組にしか属さない 応用： 人 と 仕事
離散数学 グラフのマッチング グラフのマッチング 辺で結ばれた2つの頂点を「組」にする 各頂点は，1つの組にしか属さない 応用： 人 と 仕事 学生 と 研究室

18 離散数学 アルゴリズム 目標： 組に属さない頂点数を最小にする O(m n) のアルゴリズムが知られている 辺の重みの和を最大にする etc