無向グラフ
𝑎
節点、頂点(vertex)
辺（edge)
𝑏
節点𝑎と節点𝑏が隣接
𝑐
𝑒
𝑑
𝑉 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}
𝐸 = {(𝑏,
{(𝑎, 𝑎),
𝑏), (𝑎, 𝑐), (𝑏, 𝑒), (𝑐, 𝑑), (𝑐, 𝑒), (𝑑, 𝑒)}
有向グラフ
節点（node)
𝑏
𝑎
弧(arc)
𝑐
𝑒
𝑑
𝑉（または𝑁） = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}
𝐸（または𝐴） = { 𝑎, 𝑏 , 𝑎, 𝑐 , 𝑏, 𝑒 , 𝑐, 𝑒 , 𝑒, 𝑐 , 𝑑, 𝑐 , (𝑑, 𝑒)}
多重グラフと辺ラベル
梅田
多重辺
阪急
阪神
三宮
辺ラベルにより区別
各辺はラベルを加えた3項組で表現 e.g.(梅田，三宮, 阪急)
重みつきグラフ
4
3
2
2
2
1
部分グラフ
𝑏
𝑎
𝑐
𝑒
𝑑
同型グラフ
𝑝
𝑎
𝑏
𝑒
𝑐
𝑞
𝑡
𝑟
𝑑
𝑎
𝑏
𝑐
𝑑
𝑒
𝑝
𝑞
𝑟
𝑠
𝑡
𝑠
同型グラフ
𝑎
𝑏
𝑝
𝑞
𝑐
𝑑
𝑟
𝑠
𝑎
𝑏
𝑐
𝑑
𝑝
𝑞
𝑟
𝑠
節点の次数
次数: 0
孤立点
次数：4
偶節点
次数：1
奇節点
有向グラフの次数
𝑝
入口
入次数 = 0
出口
𝑟
𝑞
出次数 = 0
𝑠
𝑡
入次数 = 2
出次数 = 1
径路
径路
径路の長さ： 径路を構成する辺の数＝5
小道
小道
小道： 辺が重複しない
順路
順路
順路： 節点が重複しない
径路、小道、順路、閉路
径路（walk）
小道（trail）
順路（path）
閉路と単純閉路
単純閉路
閉路： 両端（始点と終点）が同じ径路
単純閉路： 両端のみが同じ
有向グラフの径路

有向径路： 有向辺の向きに沿った径路
径路： 有向辺の向きを無視した径路
有向小道：
 有向順路：
 有向閉路：
 逆有向辺：

有向辺の向きに沿った小道
有向辺の向きに沿った順路
有向辺の向きに沿った閉路
逆向きの辺 (a,b)⇒(b,a)
無向グラフの連結性
1
𝑎
2
4
1
4
𝑐
3
𝑏
連結グラフ
非連結
𝑎, 𝑏間の距離: 𝑑 𝑎, 𝑏 = 1
2
グラフの直径： max 𝑑(𝑥, 𝑦) = 𝑑 𝑎, 𝑐 = 5
切断点（cut point）、橋（bridge）
切断点
橋
有向グラフの連結性
強連結： 両方向の有向順路が存在
 弱連結： （向きを無視する）順路が存在

強連結グラフ （辺を一つ除去すると弱連結になる）
p.157の図
完全グラフ
正則グラフ
p.157の図
2部グラフ
完全2部グラフ
（無向）木
p.157の図
(a), (b)
a
b
e
c
d
グラフ G
完全グラフ GK
補グラフ G’
p.157の図(c)
a
b
補グラフ
e
c
d
同型
一致
a
e
自己補グラフ
c
b
d

第15回