第10章

Information Mathematics 2014
第10章
木グラフ
Information Mathematics 2014
木グラフ
• 木グラフ
– 任意のノード間に順路が1つだけ存在するグラフ
＝閉路が存在しない連結グラフ
＝ n-1 個の辺を持つ n ノードの連結グラフ
＝ n-1 個の辺を持つ閉路が存在しないグラフ
• 根付き木
– 有向木の一種
• 矢印の元を親ノード、先を子ノード
• 下が矢印の向きとして、矢印を省略することが多い
– 一番上のノード＝根ノード
– 下にノードがないノード＝葉ノード
– 1つのノードから2つ以下の辺が出る木＝二分木
省略
Information Mathematics 2014
順序木
根
葉
• 順序関係を導入した木
d1
c1
– ノード x,y について、
d2
• x > y ： x は y の親である
• x >+ y ： x は y の祖先である（推移的閉包）
• x ≧t y ：x は y の祖先である（ただし、x は x の祖先
である＝反射的推移的閉包）→順序関係となる
• 木構造の半順序関係
– 比較できない要素があるため
b1
c2
d3
c3
a1
c4
– ノード x,y について、
• x ≧o y ： x の祖先は y の祖先の祖先であるか、x
は y の兄である
（ただし、x は x の兄である）
• 木構造の全順序関係
– すべての要素で順序を比較可能 → 順序木
d4
b2
d5
c5
d6
b3
d7
c6
d8
Information Mathematics 2014
順序木のリスト表現
• 順序木は全ノードに順序を付けることが
可能
• リストとして表現できる
– 先頭に根ノードを書き、その後に部分木をカン
マで区切って書き、全体を括弧で囲む
– 再帰的に表現する
– ただし、葉ノードは括弧では囲まない
• （親, 兄, 弟・・・）の形
– 兄弟が木になっていれば、それも（）で囲
む
a
c
b
d
i
e
j
f
k
g
l
h
m
n
(d,i,j)
(b,(d,i,j),e,(f,k,l))
(a,(b,(d, i,j),e,(f,k,l)),(c,g,(h,m,n,o))
o
Information Mathematics 2014
木の探索
迷路
横型探索
S
S
A
B
A
C
B
C
D
D
F
E
E
F
D
G
C
G
縦型探索
S
• OpenList ：探索を待っているノード
A
• 最初は開始ノードだけ
• たどった後は、続くノードを追加し
て自分はClosedListへ
• このリストが FIFO → 横型探索
C
B
D
E
C
• このリストが LIFO → 縦型探索
F
• ClosedList ：探索が終わったノード
• たどり終わったノードのリスト
G
S
Information Mathematics 2014
縦型探索の実際
• OpenList (LIFO)
–
–
–
–
–
–
–
–
• ClosedList
(S[ ])
(A[S],C[S])
(B[A],D[A],C[S])
(E[B],D[A],C[S])
(D[A],C[S])
(C[D],C[S])
(F[C],C[S])
(G[F],C[S])
S
A
–
–
–
–
–
–
–
–
()
(S[ ])
(S[ ],A[S])
(S[ ],A[S],B[A])
(S[ ],A[S],B[A],E[B])
(S[ ],A[S],B[A],E[B],D[A])
(S[ ],A[S],B[A],E[B],D[A],C[D])
(S[ ],A[S],B[A],E[B],D[A],C[D],F[C])
C
B
S
A
B
C
D
E
F
G
D
E
C
F
G
S
Information Mathematics 2014
横型探索の実際
• OpenList (FIFO)
–
–
–
–
–
–
–
–
• ClosedList
–
–
–
–
–
–
–
–
(S[ ])
(A[S],C[S])
(C[S],B[A],D[A])
(B[A],D[A],D[C],F[C])
(D[A],D[C],F[C],E[B])
(D[C],F[C],E[B],C[D])
(F[C],E[B],C[D],A[D])
(E[B],C[D],A[D],G[F])
S
A
B
E
()
(S[ ])
(S[ ],A[S])
(S[ ],A[S],C[S])
(S[ ],A[S],C[S],B[A])
(S[ ],A[S],C[S],B[A],D[A])
(S[ ],A[S],C[S],B[A],D[A],D[C])
(S[ ],A[S],C[S],B[A],D[A],D[C],F[C])
S
A
B
C
D
E
F
G
C
D
D
C
F
G
Information Mathematics 2014
最短径路問題
• 距離を書いた地図が与えられたとき、ある地点から別な地点までの最短
径路を求める問題
– 下の地図でAからLまでの最短径路は？
– 辺につけられた数字が距離
• 解法
– 糸を使って、実際の距離と等しい模型を作る方法
• Aの結び目とLの結び目を持って左右に引っ張ったとき、ぴんと張っている糸が求
める径路である
– ダイキストラのアルゴリズム
B
2
3
5
G
3
J
D
4
A
9
E
2
5
1
H
2
6
C
1
9
5
6
F
2
I
L
9
2
K
2
Information Mathematics 2014
ダイキストラのアルゴリズム
• Aから近い順に頂点を選び、その頂点にAからの最短径路長を割り当て
ていく方法
回
候補
決定
回
A
B
C
D
E
F
G
1
B=3,C=2,E=9
C=2
1
0
3
2
9
2
E=8,F=11
B=3
2
0
3
2
8
11
3
D=5,E=7,F=11
D=5
3
0
3
2
5
7
11
4
G=8,F=11
E=7
4
0
3
2
5
7
11
8
5
G=8,H=9,F=11
G=8
5
0
3
2
5
7
11
8
H
I
J
K
L
9
6
B
7
11
J
D
4
A
9
10
5
G
3
3
8
9
2
E
2
5
1
H
2
6
C
1
9
5
6
F
2
I
L
9
2
K
2
Information Mathematics 2014
ダイキストラのアルゴリズム
• Aから近い順に頂点を選び、その頂点にAからの最短径路長を割り当て
ていく方法
回
候補
決定
回
A
B
C
D
E
F
G
H
I
J
K
L
1
B=3,C=2,E=9
C=2
1
0
3
2
9
2
B=3,E=8,F=11
B=3
2
0
3
2
8
11
3
D=5,E=7,F=11
D=5
3
0
3
2
5
7
11
4
E=7,G=8,F=11
E=7
4
0
3
2
5
7
11
8
5
G=8,H=9,F=11
G=8
5
0
3
2
5
7
11
8
9
6
F=11,H=9,J=13
H=9
6
0
3
2
5
7
11
8
9
13
7
F=10,J=13,K=15
,L=18
F=10
7
0
3
2
5
7
10
8
9
13
15
18
8
0
3
2
5
7
10
8
9
12
13
15
18
8
I=12,J=13,K=15,
L=18
I=12
9
0
3
2
5
7
10
8
9
12
13
14
18
9
J=13,K=14,L=18
J=13
10
0
3
2
5
7
10
8
9
12
13
14
18
10
K=14,L=16
K=14
11
0
3
2
5
7
10
8
9
12
13
14
16
11
L=16
L=16
Information Mathematics 2014
第10章終了

Download Report