卒業研究関係の話題 (Tree decomposition)

卒業研究
Treedecompositionを生成する
ヒューリスティックアルゴリズムの幅
に関する評価実験
4年:山下 由展
目次
 Tree
decompositionの定義について
 Tree decompositionを生成するヒューリス
ティックアルゴリズムの紹介
 卒業研究について
Tree decompositionの定義
グラフG=(V,E)に対して、木TとV(G)のある部分
集合族X={Xi|i∈V(T)}の対(T,X)を考える。
木T X 1
1
Xp
Xp=V(G)の
ある部分集合
p
※pはTの頂点の番号(ここでは1≦p≦|V(G)|)
Tree decompositionの定義
グラフG=(V,E)に対して、木TとV(G)のある部分
集合族X={Xi|i∈V(T)}の対(T,X)を考える。
1
V(G)={a,b,c,d,e,f}だとすると
f
(T,X)
(T,X)
1
3
2
b,c,d,e
a,b
a,b
3
e,f
d
4
c
2
5
c,d (T,X)は2nm通りある e,f
n=|V(G)|
d,e,f
mは木の頂点数
Tree decompositionの定義
グラフGに対して、木TとV(G)のある部分集合族
X={Xi|i∈V(T)}の対(T,X)が以下の3つの条件を満
たすとき、(T,X)をGのTree decompositionという。
(1)∪i∈V(T)Xi=V(G) 頂点集合{1,2,3,4,5,6,7}
G).
(T,X)
1
2
1 1,2,4
5
2
3
4
7
1,3,4
4
3
5
6
4,6,7
3,4,5
4,5,6
Tree decompositionの定義
グラフGに対して、木TとV(G)のある部分集合族
X={Xi|i∈V(T)}の対(T,X)が以下の3つの条件を満
たすとき、(T,X)をGのTree decompositionという。
(2)∀v,w∈V(G)[(v,w)∈E(G)⇒∃i∈V(T)[v,w∈Xi]]
G).
(T,X)
1
2
1
1,2,4
5
2
3
4
7
1,3,4
4
3
5
6
4,6,7
3,4,5
4,5,6
Tree decompositionの定義
グラフGに対して、木TとV(G)のある部分集合族
X={Xi|i∈V(T)}の対(T,X)が以下の3つの条件を満
たすとき、(T,X)をGのTree decompositionという。
(3)∀i,j,k∈V(T)[jがTにおけるiからkへの道上にある
⇒Xi∩Xk⊆Xj
G).
1
1
2
(T,X)
1,2,4
5
2
3
4
7
1,3,4
4
3
5
6
4,6,7
3,4,5
4,5,6
Tree decompositionの定義

幅=maxi∈I|Xi|-1
1,2,4
1,3,4
4,6,7
3,4,5
4,5,6
幅=2
木幅=グラフGからつくられるTree decompositionがもつ
幅のなかで一番小さい値

目次
 Tree
decompositionの定義について
 Tree decompositionを生成するヒューリス
ティックアルゴリズムの紹介
 卒業研究について
s-t separating set
グラフG=(V,E)の頂点sから頂点tへのどんな道も
集合S(⊆V∖{s、t})の頂点を通る時、この集合S
をs-t separating setという。
例)
sS
t
Minimum separating vertex setの定義
グラフG=(V,E)の互いに隣接しない頂点全ての組み
合わせでst-separating setをすべて求めた時、
その中で位数が最小のものを
minimum separating vertex setと呼ぶ。
t
s
t
s
t
Tree decompositionを生成するヒューリスティックアルゴ
リズム(Aire M.C.A Koster等の論文に載っているもの)
V(G)={v1、v2、…、vn}
(T,X)
v1、v2、…、vn
G=(V、E)
|i|=1 かつ
頂点を分割して幅の小さい X1=Vの
Tree decompositionを
Tree decomposition
つくる
をつくる
Tree decompositionを
つくる操作をする
∃i∈I:
Gi≠クリーク
yes
no
G=(V、E)
はグラフで、
(T,X)はGのTree
Decomposition
である(ここで、
T=(I,F)はノードI
と辺Fの木。
そして、X={Xi:i∈I}
はVの部分集合族
目標の
Tree decomposition
完成
準備
ここで、G =(V 、E )を次で定める。
i
i
i
ここで、N(i)は頂点k
に隣接する頂点の集合
Cはクリーク
Vi=Xi、Ei=E(G[Xi])∪E(∪k∈N(i)C(Xi∩Xk))
d
i
b
f
k
G3
j
G).
h
d
a
e
c
g
1
2
3
5
abd acd cde def ・・・
e
c
Gの ↑
4 egh Tree decompositionの作成途中
Tree decompositionを生成するヒューリスティックアルゴ
リズム(Aire M.C.A Koster等の論文に載っているもの)
G=(V、E)
|i|=1 かつ
X1=Vの
Tree decomposition
をつくる
Tree decompositionを
つくる操作をする
∃i∈I:
Gi≠クリーク
yes
no
G=(V、E)
はグラフで、
(T,X)はGのTree
Decomposition
である(ここで、
T=(I,F)はノードI
と辺Fの木。
そして、X={Xi:i∈I}
はVの部分集合族
目標の
Tree decomposition
完成
Tree decompositionを生成するMinimum
ヒューリスティクアルゴリズムseparating
ii0
Xi0
i
Xi0= S
i1
Xi1
i2
set S
S
Xi1 vertex
はグラフ
Yi1
はその
Gi[ViG
/S]
i
YXim-1
頂点集合
im-1
im
Xi2
Xim
・・・
Xk、k∈N(i)
Yi2
Xi2
S
・・・
S
Yim
Xim
Gi[Vi/S]はm個の S
連結成分に分割された
とする。
グラフからTree decompositionをつくっ
てなにか役にたつの?
グラフのTreewidthを定数で押さえることができる場
合、最大独立集合問題やハミルトンサイクル問題など
のNP困難問題を多項式時間でとくことができる。
実演Java
目次
 Tree
decompositionの定義について
 Tree decompositionを生成するヒューリス
ティックアルゴリズムの紹介
 卒業研究について
Minimum
何ペアかの頂点ペアを
卒業研究内容
ランダムに選び、その頂点
separating
ペアのst separating vertex setの
vertex set S
はグラフ 中で位数最小のもの
Xi i
はその G [V /S]
i i Gi
頂点集合
・・・
Xk、k∈N(i)
・・・
Sは何ペアかの頂点ペアの
中で位数最小の
minimum st separating vertex set
頂点ペアを何ペアか選択する時
Giの頂点数の1割、2割、3,4,5,
6,7、8、9,10割の場合の10通り試している。
それぞれについて、できた
Tree decompositionの
幅を評価する
この過程を3回繰り返す
現在の状況
200個の
Tree decompositionの
幅の平均値を
それぞれ求める
頂点数10、20
のグラフそれぞれ200個
Tree decomposition
Tree decompositionを作る際、
Minimum separating vertex setを用いた
アルゴリズム,
頂点数の1割をランダムに選び、その頂点ペアの
st separating setの位数の最小のものを
採用したアルゴリズム、
頂点数の2割の・・・、頂点数の3割の・・・、・・・
、頂点数の10割の・・・。
現在の状況
4.6
幅
4.5
頂点数10のグラフ
200個をそれぞれの方法で
Tree decompositionに変えて、
その幅の平均を求める操作を
それぞれ3回ずつ行った時の
幅の平均値の分布
minimum
sepaの幅
4.4
1割ペア
10割ペア
現在の状況
12
幅
11.9
頂点数20のグラフ
200個をそれぞれの方法で
Tree decompositionに変えて、
その幅の平均を求める操作を
それぞれ3回ずつ行った時の
幅の平均値の分布
11.8
minimum
sepaの幅
11.7
1割ペア
10割ペア
これからの課題
グラフの頂点数と生成数を増やしていったり、ランダム
に生成したグラフだけではなく、ある特定の種類のグ
ラフにたいしても同様のことをやってみるなど、いろい
ろな場合を試してみる。
Fin