グラフと木
グラフ
v１
v4
v2
v3
G=(V,E)
v1
v2
v3
v4
v1 v2
0 1
0 0
0 0
0 1
v3
0
1
0
1
v4
1
0
0
0
隣接行列
･
2 ･
･
3 /
/
･
2 ･
4 /
3 /
隣接リスト
V={v1,v2,v3,v4 }
E={(v1,v2), (v1,v4), (v2,v3), (v4,v2), (v4,v3)}
グラフ（経路）
v１
v6
v5
v１
v6
v5
v2
v3
v4
v2
v3
v4
単純な経路（パス）
（ v１,v6,v2)
単純でない経路
（ v１,v6,v5,v4,v6,v2)
グラフ（閉路）
v１
v6
v5
v１
v6
v5
v2
v3
v4
v2
v3
v4
単純な閉路（サイクル）
（ v１,v2,v6,v１)
単純でない閉路
（ v１,v2,v6,v4,v5,v6,v１)
横道
•
•
•
•
•
•
•
•
「3年1組の生徒は全員仲が良い」
これを∀や∃を使って表すと？
∀x,y∈3年1組の生徒, xとyは仲が良い
では上の否定は？
「3年1組の生徒は全員仲が悪い」?
∀x,y∈3年1組の生徒, xとyは仲が悪い？
「3年1組の生徒は全員仲が良い」わけではない？
∃ x,y∈3年1組の生徒 s.t. xとyは仲が悪い
グラフ（連結グラフ）
v１
v6
v5
v１
v6
v5
v2
v3
v4
v2
v3
v4
非連結グラフ
連結グラフ
あるvi,vｊが存在し
viとvｊを結ぶ経路
が存在しない
任意のvi,vｊに対し
viとvｊを結ぶ経路
が存在する
グラフ（強連結グラフ）
v１
v6
v5
v１
v6
v5
v2
v3
v4
v2
v3
v4
強連結グラフ
任意のvi,vｊに対し
viとvｊを結ぶ経路
が存在する
強連結グラでない例
木（一般の木）
深さ0
深さ1
深さ2
深さ3
v
x
高さ(=4)
y
深さ4
根
vはxやyの親
葉
xやyはvの子
XXを持たない頂点をYYと呼ぶ
木（２分木）
子を高々2個しか持たない木
v
r
l
vの右の部分木
vの左の部分木
lはvの左の子
rはvの右の子
木（完全２分木）
n：頂点数
木の高さ= log (n+1)-1
葉の個数= (n+1)/2
木（木のバランス）
バランスの悪い木
木の走査
1回目の訪問
2回目の訪問
先行順走査
3回目の訪問
木の走査
1
先行順走査
木の走査
1
2
先行順走査
木の走査
1
2
3
先行順走査
木の走査
1
2
3
4
先行順走査
木の走査
1
2
3
4
先行順走査
木の走査
1
2
3
4
先行順走査
木の走査
1
2
3
4
先行順走査
木の走査
1
2
3
4
5
先行順走査
木の走査
1
2
3
4
5
先行順走査
木の走査
1
2
3
4
5
先行順走査
木の走査
1
2
3
4
5
先行順走査
木の走査
1
2
3
4
5
先行順走査
木の走査
1
2
3
4
5
先行順走査
木の走査
1
2
3
4
5
先行順走査
木の走査
1
6
2
7
3
4
5
9
8
先行順走査