離散数学 06. グラフ 序論 五島.

Presentation on theme: "離散数学 06. グラフ 序論 五島."— Presentation transcript:

1 離散数学 06. グラフ 序論 五島

2 グラフとは 絵で書けばこういうもの 頂点（vertex, node）の集合 と， 辺（edge, arc） の集合 ただし，幾何的な情報：
離散数学 グラフとは 絵で書けばこういうもの 頂点（vertex, node）の集合 と， 辺（edge, arc） の集合 ただし，幾何的な情報： 点の位置， 線分の長さや， そもそも線分であることなど は重要ではない 2点間に「関係がある」という情報だけが重要

3 どんな問題を考えるか? ありとあらゆる無数の問題 最短路 全域木，最小木 最大流れ 最小カット マッチング 彩色 最長路 巡回 平衡分割
離散数学 どんな問題を考えるか? ありとあらゆる無数の問題 最短路 全域木，最小木 最大流れ 最小カット マッチング 彩色 最長路 巡回 平衡分割 同型判定 埋め込み判定 etc.

4 離散数学 グラフと現実はどのように対応しているか 様々な問題がグラフ上の問題としてモデル化，定式化される

5 「わかりやすい」例 離散数学 交通網 分子構造 頂点： 都市や駅 頂点： 原子 辺 ： 道路や路線 辺 ： 結合 コンピュータ・ネットワーク
辺　： 道路や路線 辺　： 結合 コンピュータ・ネットワーク 履修ガイド 頂点： 端末やスイッチ 頂点： 科目 辺　： ケーブル 辺　： 科目間の依存関係 WWW 人間関係 (social network) 頂点： ページ 頂点： 人間， 辺　： リンク 辺　： 関係（知人，etc.） ディジタル回路 頂点： 論理素子 辺　： 配線

6 少し自明でない例 (1/2) 地図 頂点： 国や地域 辺 ： 隣接関係 迷路 頂点： 交差点 辺 ： 隣の交差点
離散数学 少し自明でない例 (1/2) 地図 頂点： 国や地域 辺　： 隣接関係 迷路 頂点： 交差点 辺　： 隣の交差点 機械語プログラム（コントロール・フロー・グラフ） 頂点： 命令 辺　： 「次の命令」 非分岐命令： その直後の命令 　分岐命令： そのターゲット

7 少し自明でない例 (2/2) ゲームetc.の状態遷移 頂点： 状態 辺 ： 1手で移れる状態の対 時刻（分刻み）を考慮した乗り換え案内
離散数学 少し自明でない例 (2/2) ゲームetc.の状態遷移 頂点： 状態 辺　： 1手で移れる状態の対 時刻（分刻み）を考慮した乗り換え案内 頂点： (時刻, 駅) 辺　： 可能な移動（または移動しない）手段 (t, A)  (t + 1, A) ： A 駅で 1分 待つ (t, A)  (t', B) ： 時刻 t にA 駅，t' にB 駅を通る電車がある 文書クラスタリング 頂点： 文書 辺　： 文書の対がどのくらい似ているか？

8 離散数学 グラフの用語

9 数学的定義 グラフ G = V, E V : 頂点の集合 E : 辺の集合 E  V  V ：頂点間の関係 よく使われる記号
離散数学 数学的定義 グラフ G = V, E V : 頂点の集合 E : 辺の集合 E  V  V ：頂点間の関係 よく使われる記号 頂点： u, v, i, j, a, b, ... 辺　： e, (u, v), u  v, ... 右のグラフ G = V, E V = {a, b, c, d} E = {e1, e2} = {(a, b), (b, c)} a d e1 e2 b c G

10 有向 / 無向 グラフ 有向（ゆうこう，directed）グラフ (a, b) と (b, a) を区別する a → b
離散数学 有向 / 無向 グラフ 有向（ゆうこう，directed）グラフ (a, b) と (b, a) を区別する a → b 無向（むこう，undirected）グラフ (a, b) と (b, a) を区別しない 無向グラフ 有向グラフ

11 次数 次数 (degree) ある頂点につながっている辺の数 入次数 と 出次数（有向グラフの場合） k-正則グラフ
離散数学 次数 次数 (degree) ある頂点につながっている辺の数 入次数 と 出次数（有向グラフの場合） k-正則グラフ すべての頂点の次数が k

12 重み 重み無し (unweighted) グラフ 辺があるかないか 重みつき (weighted) グラフ 辺があるかないか ＋
離散数学 重み 重み無し (unweighted) グラフ 辺があるかないか 重みつき (weighted) グラフ 辺があるかないか ＋ 辺に数値を付加 「重み」，「コスト」

13 部分グラフ (subgraph) G' = V', E' と G = V, E に対し，V' ⊆ V かつ E' ⊆ E
離散数学 部分グラフ (subgraph) G' = V', E' と G = V, E に対し，V' ⊆ V かつ E' ⊆ E G ： G' の親グラフ，拡大グラフ (supergraph?) G' ： G の部分グラフ (subgraph)

14 道 (1/2) 道 (path) 隣接する頂点の系列（からなる部分グラフ） 表記： u1  u2  ...  un
離散数学 道 (1/2) 道 (path) 隣接する頂点の系列（からなる部分グラフ） 表記： u1  u2  ...  un u1 * un （推移的閉包の記号） u1 から un へ到達可能 (reachable)： u1 から un への道が存在する u1 u3 un−1 u2 un

15 道 (2/2) 単純路 (simple path) 同じ頂点を2度含まない道 閉路 (closed path)，ループ (loop)
離散数学 道 (2/2) 単純路 (simple path) 同じ頂点を2度含まない道 閉路 (closed path)，ループ (loop) 始点と終点が一致する道 (u1 = un) 単純閉路 (simple closed path, simple loop) 同じ頂点を2度含まない閉路 （始点と終点以外） u3 u2 u1 単純路ではない道 u3 u2 u1 単純閉路ではない閉路

16 連結 連結 (connected)（無向グラフの場合） 「全体がひとつにつながっている」 任意の2頂点間に道が存在する 有向グラフの場合：
離散数学 連結 連結 (connected)（無向グラフの場合） 「全体がひとつにつながっている」 任意の2頂点間に道が存在する 有向グラフの場合： 連結 (connected) 辺の向きを無視して，任意の2頂点間に道 無向グラフが連結 強連結 (strongly connected) 辺の向きも考えて，任意の2頂点間に道 強連結 連結だが強連結でない

17 連結成分 （強）連結成分： あるグラフの部分グラフで，（強）連結かつ極大なもの． （強）連結で極大：
離散数学 連結成分 （強）連結成分： あるグラフの部分グラフで，（強）連結かつ極大なもの． （強）連結で極大： それ以上頂点を加えると（強）連結でなくなる （有向グラフの）強連結成分の言い換え： ある頂点 u に対して， u 自身と u * v と v * u がともに存在するような v のすべて を頂点とする部分グラフ 「行って帰ってこれる頂点全部」

18 循環 / 非循環グラフ 木 (tree)： 森のうち，連結であるもの 木 ⊆ 森 森の各連結成分は木 森は木の集合 無向
離散数学 循環 / 非循環グラフ 無向 Undirected 有向 Directed 閉路なし 非循環グラフ Acyclic 森 forest DAG 閉路あり 循環グラフ Cyclic 無向循環 グラフ 有向循環 木 (tree)： 森のうち，連結であるもの 木 ⊆ 森 森の各連結成分は木 森は木の集合 森

19 根 (root) （連結非循環グラフの）根 (root)： 頂点を1つ選んで， それが一番「上」にあると考える 木（無向）：
離散数学 根 (root) （連結非循環グラフの）根 (root)： 頂点を1つ選んで， それが一番「上」にあると考える 木（無向）： どの頂点も根になり得る 根付き木 (rooted tree) DAG（有向）： 根がない場合もある どれが根？ 根のない DAG

20 離散数学 循環 / 非循環グラフの例 非循環グラフ 循環グラフ 木 木 無向循環グラフ DAG DAG DAG 有向循環グラフ

21 疎 と 密 疎 (sparse) なグラフ 辺の数が少ない 通常，頂点数 n に対して O(n)，O(n log n)
離散数学 疎 と 密 疎 (sparse) なグラフ 辺の数が少ない 通常，頂点数 n に対して O(n)，O(n log n) 密 (dense) なグラフ 辺の数が多い 完全グラフ (complete graph) すべての頂点間を結ぶ辺が存在するグラフ (E = V  V)

22 離散数学 グラフの操作

23 グラフに対する基本的な操作 操作 adjacents(u) : 頂点 u に隣接する頂点を（すべて）列挙する (u, v)  E :
離散数学 グラフに対する基本的な操作 操作 adjacents(u) : 頂点 u に隣接する頂点を（すべて）列挙する (u, v)  E : 2頂点 u, v 間に辺が存在するかどうかを調べる またはその重みを得る これらの操作が，少ないメモリで効率的に行えることが目標

24 離散数学 グラフ表現に用いるデータ構造 典型的なデータ構造 行列表現（密なグラフ用） リスト表現（疎なグラフ用）

25 密なグラフ用の表現（2次元行列） 頂点の集合 V = { 0, 1, ..., n – 1 } とする
離散数学 密なグラフ用の表現（2次元行列） 頂点の集合 V = { 0, 1, ..., n – 1 } とする 辺の情報を2次元行列 M[i, j] (0  i < n, 0  j < n) に格納 重みなしグラフ M[i, j] = 1 iff (i, j)  E M[i, j] = 0 iff (i, j)  E 重みつきグラフ M[i, j] が辺 (i, j) の重み 「重み 0」と「辺がない」の区別に注意

26 離散数学 行列による表現 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 1 1 1 1 2 1 1 空欄は0 3 1 1 1 1 1 4 1 1 5 1 1 6 1 1 1 7 1 1

27 疎なグラフ用の表現（リスト） 各頂点 i に対し，その隣接頂点の集合を格納 「0 にメモリを使わない」 辺の数に比例したメモリしか使わない
離散数学 疎なグラフ用の表現（リスト） 各頂点 i に対し，その隣接頂点の集合を格納 「0 にメモリを使わない」 辺の数に比例したメモリしか使わない 疎な行列に向いている 「隣接頂点の集合」の実現 配列，リンクリスト，平衡木，ハッシュ表 ただし，疎行列（次数が定数かせいぜい log n）が前提であれば 配列・リンクリストで十分

28 離散数学 リストによる表現 1 1 2 3 4 5 6 7 1 2 3 2 1 3 3 1 4 5 6 7 4 3 5 5 4 6 6 3 5 7 7 3 6

29 オブジェクトとポインタによる表現 頂点：任意のオブジェクト (Java, C++) や構造体 (C) 辺 ：ポインタ（参照）
離散数学 オブジェクトとポインタによる表現 頂点：任意のオブジェクト (Java, C++) や構造体 (C) 辺　：ポインタ（参照） C/C++ ポインタ， Java オブジェクト参照 Java: class node { node[] adjacents; } C++: class node { int n_adjacents; node *adjacents[]; } C++/Javaオブジェクト， C 構造体 etc.

30 利害得失 メモリ消費量 (i, j)  E adjacents(i) 行列表現 O(n2) O(1) O(n) リスト表現
離散数学 利害得失 メモリ消費量 (i, j)  E adjacents(i) 行列表現 O(n2) O(1) O(n) リスト表現 O(n + m) O(d) または O(log d) O(d) ただし： 頂点数 n, 辺の数 m とする 次数の最大値を d とする オブジェクト＋ポインタを用いた表現はリストに準ずる

31 グラフアルゴリズム計算量のパラメータ 通常， n: 頂点数 m: 辺の数 (m  n2) の関数として計算量を評価する n と m
離散数学 グラフアルゴリズム計算量のパラメータ 通常， n: 頂点数 m: 辺の数 (m  n2) の関数として計算量を評価する n と m n のみで表す m  n2 なので n, m の関数は n だけの関数として上から押さえられる n と m で表す とくに，疎なグラフ（m << n2）に対して効率の良いアルゴリズム 例：O(n + m) は，疎なグラフに対しては O(n2) よりも優れている

32 離散数学 グラフ・アルゴリズム計算量のパラメータ そのほかの有用なパラメータ 最大次数 グラフの直径（単純な道の最大長）

33 これから議論する問題とアルゴリズム 易しい（多項式時間アルゴリズムが存在する）問題 問題とアルゴリズム 頂点の探索とその応用
離散数学 これから議論する問題とアルゴリズム 易しい（多項式時間アルゴリズムが存在する）問題 問題とアルゴリズム 頂点の探索とその応用 最短路(shortest path) 全域木，最小木 (minimum spanning tree; MST) 最大流と最小カット (max flow/min cut) 難しい（計算困難な）問題 有名な問題の紹介 同型判定 彩色 クリーク（完全部分グラフ）の発見 平衡分割