グラフ序論

離散数学
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)
 難しい(計算困難な)問題
 有名な問題の紹介
 同型判定
 彩色
 クリーク(完全部分グラフ)の発見
 平衡分割