卒業研究 Treedecompositionを生成するヒューリスティックアルゴリズムの幅に関する評価実験

Presentation on theme: "卒業研究 Treedecompositionを生成するヒューリスティックアルゴリズムの幅に関する評価実験"— Presentation transcript:

1 卒業研究 Treedecompositionを生成するヒューリスティックアルゴリズムの幅に関する評価実験
４年：山下　由展

2 目次 Tree decompositionの定義について Tree decompositionを生成するヒューリスティックアルゴリズムの紹介
卒業研究について

3 Tree decompositionの定義
グラフG=(V,E)に対して、木TとV（G)のある部分 集合族X=｛Xi|i∈V(T)}の対（T,X)を考える。 木Ｔ Ｘｐ＝Ｖ（Ｇ）の ある部分集合 Ｘ１ １ Ｘｐ ｐ ※ｐはＴの頂点の番号（ここでは１≦ｐ≦|V(G)|)

4 Tree decompositionの定義
グラフG=(V,E)に対して、木TとV（G)のある部分 集合族X=｛Xi|i∈V(T)}の対（T,X)を考える。 Ｖ（Ｇ）＝{a,b,c,d,e,f｝だとすると 1 （Ｔ，Ｘ） f （Ｔ，Ｘ） １ ３ 2 b,c,d,e a,b a,b 3 e,f d 4 c ２ 5 c,d (T,X)は２ｎｍ通りある e,f ｎ＝|V(G)| ｍは木の頂点数 d,e,f

5 Tree decompositionの定義
グラフGに対して、木TとV（G)のある部分集合族 X=｛Xi|i∈V(T)}の対（T,X)が以下の３つの条件を満 たすとき、(T,X)をGのTree decompositionという。 （１）∪i∈V(T)Xi=V(G) 頂点集合｛1,2,3,4,5,6,7} G). １ ２ １，２，４ （T,X) 1 5 2 ３ ４ ７ １，３，４ ４，６，７ 4 3 ４，５，６ ３，４，５ ５ ６

6 Tree decompositionの定義
グラフGに対して、木TとV（G)のある部分集合族 X=｛Xi|i∈V(T)}の対（T,X)が以下の３つの条件を満 たすとき、(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 ，4 1 5 2 ３ ４ ７ ４ ，６， ７ １，３ ，４ 4 3 ４，５，６ ３，４，５ ５ ６

7 Tree decompositionの定義
グラフGに対して、木TとV（G)のある部分集合族 X=｛Xi|i∈V(T)}の対（T,X)が以下の３つの条件を満 たすとき、(T,X)をGのTree decompositionという。 （3)∀i,j,k∈V(T)[jがTにおけるiからｋへの道上にある 　　　⇒Xi∩Xk⊆Xj G). １ ２ 1 １，２，４ （T,X) 5 2 ３ ４ ７ １，３，４ ４，６，７ 4 3 ４，５，６ ３，４，５ ５ ６

8 Tree decompositionの定義
幅＝maxi∈I|Xi|-1 木幅＝グラフＧからつくられるTree decompositionがもつ 幅のなかで一番小さい値 1,2,4 4,6,7 1,3,4 幅＝２ 4,5,6 3,4,5

9 目次 Tree decompositionの定義について Tree decompositionを生成するヒューリスティックアルゴリズムの紹介
卒業研究について

10 s-t separating set ｔ ｓ 例） グラフG=(V,E)の頂点ｓから頂点ｔへのどんな道も
集合S（⊆V∖｛ｓ、ｔ｝）の頂点を通る時、この集合S をs-t　separating setという。 例） ｔ Ｓ ｓ

11 Minimum separating vertex setの定義
合わせでst-separating setをすべて求めた時、 その中で位数が最小のものを minimum separating　vertex setと呼ぶ。 ｔ ｓ ｔ ｔ ｓ

12 Tree decompositionを生成するヒューリスティックアルゴリズム（Aire M.C.A Koster等の論文に載っているもの)
G=(V、E) はグラフで、 (T,X)はGのTree Decomposition である(ここで、 T=(I,F)はノードＩ と辺Fの木。 そして、X＝｛Xi：i∈I} はVの部分集合族 V（G）＝｛ｖ１、ｖ２、…、ｖｎ｝ G=(V、E) （Ｔ，Ｘ） ｖ１、ｖ２、…、ｖｎ |i|=1 かつ X1=Vの Tree decomposition をつくる 頂点を分割して幅の小さい Tree decompositionを つくる Tree decompositionを つくる操作をする ∃i∈I: Gi≠クリーク 目標の Tree decomposition 完成 no yes

13 準備 ここで、Gi＝(Vi、Ei)を次で定める。 Vi＝Xi、Ei＝E(G[Xi])∪E(∪ｋ∈N(i)C(Xi∩Xｋ)) d i b f
に隣接する頂点の集合 ここで、Gi＝(Vi、Ei)を次で定める。 Vi＝Xi、Ei＝E(G[Xi])∪E(∪ｋ∈N(i)C(Xi∩Xｋ)) Cはクリーク d i b f k G3 G). j h d a e c g 1 2 3 5 abd acd cde def ・・・ e c ↑ 4 Gの Tree　decompositionの作成途中 egh

14 Tree decompositionを生成するヒューリスティックアルゴリズム（Aire M.C.A Koster等の論文に載っているもの)
G=(V、E) はグラフで、 (T,X)はGのTree Decomposition である(ここで、 T=(I,F)はノードＩ と辺Fの木。 そして、X＝｛Xi：i∈I} はVの部分集合族 G=(V、E) |i|=1 かつ X1=Vの Tree decomposition をつくる Tree decompositionを つくる操作をする ∃i∈I: Gi≠クリーク 目標の Tree decomposition 完成 no yes

15 Tree decompositionを生成する ヒューリスティクアルゴリズム
Minimum separating vertex set S はグラフ Xi1 S Yi1 i0 i Xi0 Xi はその 頂点集合 Xi0 = S Gi Gi[Vi/S] Yim-1 Xim-1 i1 i2 im Xi1 Xi2 Xim Yi2 ･･･ ･･･ S ･･･ Xi2 Yim Xk、ｋ∈N(i) S Xim Gi[Vi/S]はｍ個の 連結成分に分割された とする。 S

16 グラフからTree decompositionをつくってなにか役にたつの？
グラフのTreewidthを定数で押さえることができる場 合、最大独立集合問題やハミルトンサイクル問題など のNP困難問題を多項式時間でとくことができる。

17 実演Java

18 目次 Tree decompositionの定義について Tree decompositionを生成するヒューリスティックアルゴリズムの紹介
卒業研究について

19 卒業研究内容 Minimum separating vertex set S はグラフ i Xi はその 頂点集合 Gi[Vi/S] Gi
何ペアかの頂点ペアを ランダムに選び、その頂点 ペアのst separating vertex setの 中で位数最小のもの はグラフ i Xi はその 頂点集合 Gi[Vi/S] Gi ･･･ ･･･ ･･･ Xk、ｋ∈N(i) Ｓは何ペアかの頂点ペアの 中で位数最小の minimum st separating vertex set 頂点ペアを何ペアか選択する時 Ｇｉの頂点数の１割、２割、３，４，５， ６，７、８、９，１０割の場合の１０通り試している。 それぞれについて、できた Tree decompositionの 幅を評価する

20 現在の状況 この過程を３回繰り返す ２００個の Tree decompositionの 幅の平均値を それぞれ求める
頂点数１０、２０ のグラフそれぞれ２００個 Tree decompositionを作る際、 Minimum separating　vertex setを用いた アルゴリズム, 頂点数の１割をランダムに選び、その頂点ペアの st separating setの位数の最小のものを 採用したアルゴリズム、 頂点数の２割の・・・、頂点数の３割の・・・、・・・ 、頂点数の１０割の・・・。

21 現在の状況 幅 １割ペア １０割ペア ４．６ ４．５ ４．４ 頂点数１０のグラフ ２００個をそれぞれの方法で
Tree decompositionに変えて、 その幅の平均を求める操作を それぞれ３回ずつ行った時の 幅の平均値の分布 幅 ４．５ minimum sepaの幅 ４．４ １割ペア １０割ペア

22 現在の状況 幅 １割ペア １０割ペア １２ １１．９ １１．８ １１．７ 頂点数２０のグラフ ２００個をそれぞれの方法で
Tree decompositionに変えて、 その幅の平均を求める操作を それぞれ３回ずつ行った時の 幅の平均値の分布 幅 １１．９ １１．８ minimum sepaの幅 １１．７ １割ペア １０割ペア

23 これからの課題 グラフの頂点数と生成数を増やしていったり、ランダム に生成したグラフだけではなく、ある特定の種類のグ
ラフにたいしても同様のことをやってみるなど、いろい ろな場合を試してみる。

24 Fin