離散数学 06. グラフ 序論 五島 DATE : 離散数学 グラフとは 絵で書けばこういうもの 頂点(vertex, node)の集合 と, 辺(edge, arc) の集合 ただし,幾何的な情報: 点の位置, 線分の長さや, そもそも線分であることなど は重要ではない 2点間に「関係がある」という情報だけが重要 離散数学 どんな問題を考えるか? ありとあらゆる無数の問題 最短路 全域木,最小木 最大流れ 最小カット マッチング 彩色 最長路 巡回 平衡分割 同型判定 埋め込み判定 etc. 離散数学 グラフと現実はどのように対応しているか 様々な問題がグラフ上の問題としてモデル化,定式化される 離散数学 「わかりやすい」例 交通網 分子構造 頂点: 都市や駅 頂点: 原子 辺 : 道路や路線 辺 : 結合 コンピュータ・ネットワーク 履修ガイド 頂点: 端末やスイッチ 頂点: 科目 辺 : ケーブル 辺 : 科目間の依存関係 WWW 人間関係 (social network) 頂点: ページ 頂点: 人間, 辺 : リンク 辺 : 関係(知人,etc.) ディジタル回路 頂点: 論理素子 辺 : 配線 離散数学 少し自明でない例 (1/2) 地図 頂点: 国や地域 辺 : 隣接関係 迷路 頂点: 交差点 辺 : 隣の交差点 機械語プログラム(コントロール・フロー・グラフ) 頂点: 命令 辺 「次の命令」 : 非分岐命令: その直後の命令 分岐命令: そのターゲット 離散数学 少し自明でない例 (2/2) ゲームetc.の状態遷移 頂点: 状態 辺 : 1手で移れる状態の対 時刻(分刻み)を考慮した乗り換え案内 頂点: (時刻, 駅) 辺 : 可能な移動(または移動しない)手段 (t, A) (t + 1, A) : A 駅で 1分 待つ (t, A) (t', B) : 時刻 t にA 駅,t' にB 駅を通る電車がある 文書クラスタリング 頂点: 文書 辺 文書の対がどのくらい似ているか? : 離散数学 グラフの用語 離散数学 数学的定義 グラフ G = V, E V : 頂点の集合 E : 辺の集合 E V V :頂点間の関係 よく使われる記号 頂点: u, v, i, j, a, b, ... 辺 : e, (u, v), u v, ... 右のグラフ G = V, E e1 V = {a, b, c, d} E = {e1, e2} = {(a, b), (b, c)} d a b e2 G c 離散数学 有向 / 無向 グラフ 有向(ゆうこう,directed)グラフ (a, b) と (b, a) を区別する a→b 無向(むこう,undirected)グラフ (a, b) と (b, a) を区別しない 無向グラフ 有向グラフ 離散数学 次数 次数 (degree) ある頂点につながっている辺の数 入次数 と 出次数(有向グラフの場合) k-正則グラフ すべての頂点の次数が k 離散数学 重み 重み無し (unweighted) グラフ 辺があるかないか 重みつき (weighted) グラフ 辺があるかないか + 辺に数値を付加 「重み」,「コスト」 離散数学 部分グラフ (subgraph) G' = V', E' と G = V, E に対し,V' ⊆ V かつ E' ⊆ E G : G' の親グラフ,拡大グラフ (supergraph?) G' : G の部分グラフ (subgraph) 離散数学 道 (1/2) 道 (path) u1 u3 隣接する頂点の系列(からなる部分グラフ) 表記: u1 u2 ... un u1 * un (推移的閉包の記号) u1 から un へ到達可能 (reachable): u1 から un への道が存在する u2 un−1 un 離散数学 道 (2/2) 単純路 (simple path) u3 u2 同じ頂点を2度含まない道 u1 閉路 (closed path),ループ (loop) 単純路ではない道 始点と終点が一致する道 (u1 = un) u3 単純閉路 (simple closed path, simple loop) 同じ頂点を2度含まない閉路 (始点と終点以外) u2 u1 単純閉路ではない閉路 離散数学 連結 連結 (connected)(無向グラフの場合) 強連結 「全体がひとつにつながっている」 任意の2頂点間に道が存在する 有向グラフの場合: 連結 (connected) 辺の向きを無視して,任意の2頂点間に道 ● 無向グラフが連結 強連結 (strongly connected) 辺の向きも考えて,任意の2頂点間に道 連結だが強連結でない 離散数学 連結成分 (強)連結成分: あるグラフの部分グラフで,(強)連結かつ極大なもの. (強)連結で極大: それ以上頂点を加えると(強)連結でなくなる (有向グラフの)強連結成分の言い換え: ある頂点 u に対して, u 自身と u * v と v * u がともに存在するような v のすべて を頂点とする部分グラフ 「行って帰ってこれる頂点全部」 離散数学 循環 / 非循環グラフ 無向 Undirected 有向 Directed 閉路なし 非循環グラフ Acyclic 森 forest DAG 閉路あり 循環グラフ Cyclic 無向循環 グラフ 有向循環 グラフ 木 (tree): 森のうち,連結であるもの 木⊆森 森の各連結成分は木 森は木の集合 森 離散数学 根 (root) (連結非循環グラフの)根 (root): 頂点を1つ選んで, それが一番「上」にあると考え る どれが根? 木(無向): どの頂点も根になり得る 根付き木 (rooted tree) DAG(有向): 根がない場合もある 根のない DAG 離散数学 循環 / 非循環グラフの例 非循環グラフ 循環グラフ 木 木 無向循環グラフ DAG DAG DAG 有向循環グラフ 離散数学 疎と密 疎 (sparse) なグラフ 辺の数が少ない 通常,頂点数 n に対して O(n),O(n log n) 密 (dense) なグラフ 辺の数が多い 完全グラフ (complete graph) すべての頂点間を結ぶ辺が存在するグラフ (E = V V) 離散数学 グラフの操作 離散数学 グラフに対する基本的な操作 操作 adjacents(u) : 頂点 u に隣接する頂点を(すべて)列挙する (u, v) E : 2頂点 u, v 間に辺が存在するかどうかを調べる またはその重みを得る これらの操作が,少ないメモリで効率的に行えることが目標 離散数学 グラフ表現に用いるデータ構造 典型的なデータ構造 行列表現(密なグラフ用) リスト表現(疎なグラフ用) 離散数学 密なグラフ用の表現(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」と「辺がない」の区別に注意 離散数学 行列による表現 0 0 2 0 7 1 1 3 6 5 2 3 1 1 4 5 6 7 1 1 2 1 3 1 4 4 1 1 1 空欄は0 1 1 5 1 1 1 6 1 7 1 1 1 1 1 1 離散数学 疎なグラフ用の表現(リスト) 各頂点 i に対し,その隣接頂点の集合を格納 「0 にメモリを使わない」 辺の数に比例したメモリしか使わない 疎な行列に向いている 「隣接頂点の集合」の実現 配列,リンクリスト,平衡木,ハッシュ表 ただし,疎行列(次数が定数かせいぜい log n)が前提であれば 配列・リンクリストで十分 離散数学 リストによる表現 0 2 7 1 3 4 6 5 0 1 1 0 2 2 1 3 3 1 4 4 3 5 5 4 6 6 3 5 7 3 6 3 5 7 6 7 離散数学 オブジェクトとポインタによる表現 頂点:任意のオブジェクト (Java, C++) や構造体 (C) 辺 :ポインタ(参照) Java: class node { ... node[] adjacents; } C++: class node { ... int n_adjacents; node *adjacents[]; } C++/Javaオブジェクト, C 構造体 etc. C/C++ ポインタ, Java オブジェクト参照 離散数学 利害得失 メモリ消費量 (i, j) E adjacents(i) 行列表現 O(n2) O(1) O(n) リスト表 現 O(n + m) O(d) または O(log d) O(d) ただし: 頂点数 n, 辺の数 m とする 次数の最大値を d とする オブジェクト+ポインタを用いた表現はリストに準ずる 離散数学 グラフアルゴリズム計算量のパラメータ 通常, n: 頂点数 m: 辺の数 (m n2) の関数として計算量を評価する nとm n のみで表す m n2 なので n, m の関数は n だけの関数として上から押さえられ る n と m で表す とくに,疎なグラフ(m << n2)に対して効率の良いアルゴリズム ● 例:O(n + m) は,疎なグラフに対しては O(n2) よりも優れている 離散数学 グラフ・アルゴリズム計算量のパラメータ そのほかの有用なパラメータ 最大次数 グラフの直径(単純な道の最大長) 離散数学 これから議論する問題とアルゴリズム 易しい(多項式時間アルゴリズムが存在する)問題 問題とアルゴリズム 頂点の探索とその応用 最短路(shortest path) 全域木,最小木 (minimum spanning tree; MST) 最大流と最小カット (max flow/min cut) 難しい(計算困難な)問題 有名な問題の紹介 同型判定 彩色 クリーク(完全部分グラフ)の発見 平衡分割
© Copyright 2024 ExpyDoc