離散数学

グラフの構造と種類
DDe8e4
e6e2
e1e6

A
e1e3

e10
Ce9e9e3
Fe5B

落合 秀也

Ee7e2e10CBe4Ee7e8Fe5

グラフとは• 頂点と頂点間をつなぐ線によって、物事を抽象的に捉えたもの

東京メトロ路線図の例
http://www.tokyometro.jp/station/common/pdf/network1.pdf

2

グラフによる実世界のモデル化• 交通網• 分子構造• コンピュータ・ネットワーク• 依存関係• WWW• Social Network• 頂点： 都市や駅
• 辺 ： 道路や路線• 頂点： 端末やスイッチ• 辺 ： ケーブル
• 頂点： ページ
• 辺 ： リンク• 頂点： 原子• 辺 ： 結合• 頂点： 事象
• 辺 ： 原因、結果の関係• 頂点： 人間，
• 辺 ： 関係（知人，etc.）• ディジタル回路• 頂点： 論理素子
• 辺 ： 配線

3

無線ネットワーク実験の紹介
51台の無線LAN端末を使った実験
互いに距離が近ければ無線LANでつながる
広範囲に展開したときに、どのようにつながる（ネットワークが構成される）のか？

4無線ネットワーク実験装置の概要
Linux ComputerStorage(2GByte)

Power Circuit

Battery(6.0V 2100mAh or 10Ah)

802.11b/g/n

5

無線LANの接続性を調査した実験
9932

10840333938
19573736
1146

工学部２号館34

32123525 2613222327 28 29302421
14
15
1650m

19504948
474645
44
43
4241

20

17 18

指定された地点に無線端末を設置し、無線LANでの接続関係を記録する

東大、本郷キャンパス (工学部エリア)

Deployment Pattern

6無線端末 設置の様子

屋外ビル内部

7無線LANの接続関係のグラフ化

Meshネットワークの不安定さ.mpg
Demonstration Video8

今日のテーマ：
グラフの構造・種類を知る• グラフとは• 次数とは、道とは、連結とは、閉路とは• 距離とは、直径とは• 木とは、全域木とは• ラベル付グラフ• 有向グラフ、DAG

9グラフ(Graph)を数学的に捉える• グラフGは、二つの集合で構成されている• 頂点(vertex)の集合V• 点(point)、節点(node)とも言う• 辺(edge)の集合E

De8e4• G (V, E) と書く

e6

A

e7e2

• V={A, B, C, D, E, F}• E={ e1, e2, …, e10 }• e1={A,B}, e2={A,C}, …

e1e10

Ce9e3

辺BEFe5
頂点10

単純グラフ、多重グラフ• 多重グラフ (multigraph)• 多重辺があるもの• 同一の頂点間で辺（ループ）を作っているもの
De8Ee4e6Ae7e2e1e10Ce11
頂点 E, F 間に二つの辺がある

e9e3
Be5F e12

FからFに辺がある• 広義には、多重グラフを、一般にグラフと呼び、多重辺やループのないグラフを、単純グラフ(simple graph)と11呼ぶこともある。

部分グラフ (subgraph)• グラフ G (V, E)に対し、V’⊂V、E’⊂E であり、かつ E’の各要素の両端点が、V’に含まれるとき、V’, E’ で作られるグラフ G’(V’, E’) を部分グラフと呼ぶ
De8e4e6

Ae7e2e1e10

Ce9e3
BEF

例：
V’={A, B, C, F}
E’={e2, e3, e9}とするとき、G’(V’,E)はG(V, E)の部分グラフe512

生成されたグラフ• G’がGの部分グラフで、V’が両端点となるGにおけるすべての辺、をE’が含む場合、G’(V’,E’)は、V’によって生成されたグラフである、という。
De8e4e6

Ae7e2e1e10
Ce9e3
BEFe5

例：
V’={A, B, C, F}
E’={e1, e2, e3, e5, e9}とするとき、G’(V’,E)はG(V, E)からV’によって、生成されたグラフである13

次数 (degree)• 頂点vに接続する辺の数を、頂点vの次数と呼ぶ。

deg(v)で表すv

左図の例:
deg(v)=514

道 (path)• 頂点-辺-頂点-辺-頂点-…-頂点 (ただし、同じ頂点を通らないもの) を、道(パス: path)と呼ぶ• モデル上の道を考察する上で重要な概念• 道は「辺の列」または「頂点の列」
Aで表現可能De8e4e6e7e2e10e1C(例) 右図の場合：e4, e8, e10 または A, D, E, F

e3
BEe9Fe515連結 (connectivity)• グラフGにおいて、任意の2頂点間に道が存在すれば、グラフGは連結である、という。
De8e4e6Ae1e7FFe5

連結なグラフECe9e3
Be6Ae10Ce8Ee7e2e1DBe5

連結でないグラフ 16

k-閉路 (k-cycle)• 頂点-辺-頂点-辺-頂点-…-頂点 (ただし、最初と最後が同じ頂点である以外、同じ頂点を通らないもの) を、閉路と呼ぶ• 閉路の辺の数に着目し、k-閉路 (k個の辺がある)
Aと呼ぶことがある。
(*) なお、kは3以上
e1（例） 右図の場合は、k=4の閉路である

D

e8e4e6e7e2e10Ce9e3BEFe517

無閉路(acyclic, cycle-free)グラフ• 閉路のないグラフ
FAHEB

GHE
B

DCF

ADC

退化木

G連結グラフ連結でないグラフ

木 (tree)森 (forest)18

全域木 (spanning tree)• グラフGのすべての頂点で構成される木• 無閉路• 連結である• すべての頂点に到達可能D• 全域木の作り方は一つではない• 何通りかある• 最小全域木の作り方は後日紹介

e8Ee4e6Ae7e2e1e10Ce9e3BFe519

距離(distance)、直径(diameter)• 2頂点間の距離: d(u,v)• 頂点u、頂点v間の最短道の辺の数のこと
FAHEB

右図の場合：
d(A,C)=2d(B,H)=3

D

直径は 3CG• グラフGの直径• G上の任意の頂点u, 頂点v間の距離の最大値のこと

20

ラベル付グラフ (labeled graph)• 頂点または辺に、ラベル（or データ）が与えられているグラフ（例）• 頂点: インターネット・ルータの名前• 辺: 回線の通信帯域 (Mbps)

10F

30A

51015H

E35

B20

D 1020C

103015

ラベル付グラフの代表的問題
・ 最短経路問題
・ 最大流量問題

G21

有向グラフ(directed graph, digraph)• 有向グラフDは、二つの集合で構成されている• 頂点(vertex)の集合V• 点(point)、節点(node)とも言う• 弧(arc): 頂点の順序対の集合A

De8e4• D (V, A) と書く

e6Ae7e2• V={A, B, C, D, E, F}• A={ e1, e2, …, e10 }• e1=<B,A>, e2=<C,A>, …

e1e10

C

e9e3

弧EB

Fe5
頂点

向きの無いグラフを、無向グラフと呼ぶこともある

22

次のものも有向グラフ• 多重弧のあるもの• 同一頂点間の弧(ループ)があるもの
 つまり、多重グラフの辺に向きがついたもの
DEAC
F
B
23

有向グラフの諸々 (1/2)
uv

uで始まり(begin) vで終わる(end)右図の例では入次数: 3
出次数: 4

入次数(indegree) 出次数(outdegree)
入次数が0

入口(source)

出次数が0出口(sink)24

有向グラフの諸々 (2/2)• 道(path)u• 半道(semipath)v
uからvへの道uuからvへの半道v
25

有向グラフの３種類の連結性• 強連結• 任意の頂点u, v間を行き来できる• 任意の頂点u, v間で双方向に道がある• 片方向連結• 任意の頂点u, v間で、少なくとも片方向は行ける• 任意の頂点u, v間で道がある• 弱連結• 任意の頂点u, v間が、弧ではつながっている• 任意の頂点u, v間で半道がある
26

有向非巡回グラフ
Directed Acyclic Graph (DAG)• 閉路の無い有向グラフ• 半順序性を持つ

DAE

B
CFG

• トポロジカルソートにより、頂点を一列に並べることができる(全順序に対応付けできる)• 上図の場合: A, D, B, E, C, F, G など
• ジョブのスケジューリング等で使われる
27

今日のテーマ：
グラフの構造・種類を知る• グラフとは• 次数とは、道とは、連結とは、閉路とは• 距離とは、直径とは• 木とは、全域木とは• ラベル付グラフ• 有向グラフ、DAG28

今後の予定• 5月27日： 探索アルゴリズム• 深さ優先探索、幅優先探索• パトリシア木• 6月3日： 最短経路問題• ベルマンフォード法、ダイキストラ法• 6月10日: 休講

29