卒業研究 木分解ヒューリスティック アルゴリズムの性能評価実験 ～アルゴリズムの改良の考察と そのプログラム作成～ ４年：山下　由展

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

木分解の定義 木Ｔ Ｘｐ＝Ｖ（Ｇ）の ある部分集合 Ｘ１ １ Ｘｐ ｐ G=(V,E)：連結な単純グラフ (T,X):T・・木、X={Xi⊆V(G)[i∈V(T)]} 木Ｔ Ｘｐ＝Ｖ（Ｇ）の ある部分集合 Ｘ１ １ Ｘｐ ｐ ※ｐはＴの頂点の番号（ここでは１≦ｐ≦|V(G)|)

木分解の定義 （１）∪i∈V(T)Xi=V(G) 頂点集合｛1,2,3,4,5,6,7} １ ２ １，２，４ ３ ４ ７ ４，６，７ ⇒TとX={Xi⊆V(G):i∈V(T)}が次の条件(1)(2)(3)を満たす。 （１）∪i∈V(T)Xi=V(G) 頂点集合｛1,2,3,4,5,6,7} １ ２ １，２，４ 1 5 2 ３ ４ ７ ４，６，７ ３，４，６，７ １，３，４ 4 3 ４，５，６ ５ ６ ３，４，５ ２，５ （T,X) G

木分解の定義 （2)∀v,w∈V(G)[(v,w)∈E(G)⇒∃i∈V(T)[v,w∈Xi]] １ ２ 1，2 ，4 ３ ４ ７ ４ ，６， (T,X)がＧの木分解 ⇒TとX={Xi⊆V(G):i∈V(T)}が次の条件(1)(2)(3)を満たす。 （2)∀v,w∈V(G)[(v,w)∈E(G)⇒∃i∈V(T)[v,w∈Xi]] １ ２ 1，2 ，4 1 5 2 ３ ４ ７ ４ ，６， ７ １，３ ，４ 4 3 ４，５，６ ３，４，５ ５ ６ G （T,X)

木分解の定義 １ ２ １，２，４ ３ ４ ７ １，３，４ ４，６，７ ４，５，６ ３，４，５ ５ ６ G （T,X) (T,X)がＧの木分解 ⇒TとX={Xi⊆V(G):i∈V(T)}が次の条件(1)(2)(3)を満たす。 （3)∀i,j,k∈V(T)[jがTにおけるiからｋへの道上にある 　　　⇒Xi∩Xk⊆Xj １ ２ 1 １，２，４ 5 2 ３ ４ ７ １，３，４ ４，６，７ 4 3 ４，５，６ ３，４，５ ５ ６ G （T,X)

木分解の定義 1,2,4 4,6,7 1,3,4 幅＝２ 4,5,6 3,4,5 幅＝maxi∈I|Xi|-1(ここではtwD(G)で表す) 木幅＝min{twD(G)} D 1,2,4 4,6,7 1,3,4 幅＝２ 4,5,6 3,4,5

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

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

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

木分解を生成するヒューリスティックアルゴリズム（Aire M.C.A Koster等の論文に載っているもの) 操作 このアルゴリズムの概要 Ｇ０ Gi V(G)={v1,v2,…,vn} ≠クリーク Ｇ０' Gi' ０ ｖ１、ｖ２、…、ｖｎ 木分解 i j グラフＧ ・・ ・・・ |Xi|最大 すべての Gi(i∈V(T))がクリークになるまで |Xj|最大

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

準備 ここで、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の 木分解の作成途中 egh

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

木分解を生成する ヒューリスティクアルゴリズム 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

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

卒業研究内容 辺の数 最大 Ｇｉ [Vi/S] はグラフ i ・・・ Xi はその 頂点集合 ・・・ ･･･ ･･･ Xk、ｋ∈N(i) Minimum Separating Vertex set (ここではＳとする) 辺の数は すべて同じとは 限らない。 Minimum separating Vertex setで誘導される Giの誘導部分グラフ

卒業研究内容 i i0 無駄にクリークに ならないように 努める Ｘｉ０ Ｘｉ Ｇｉ [Vi/S] Ｘｉ１ Ｘi2 Xim ・・・ ・・・ E[Gi[minimum separating vertex set]] 最大 E[Gi[Vi/S]]最小 |V[Gi[Vi/S]]|同じ

実演Java

関連データ 論文のものの 方が幅が小さい 卒研のものの 方が幅が小さい 同じ 標本数 頂点数 ５０ １０ ０ ２ ４８ ５０ ４ ９ ５０ ３７ １ １００ ０ ０ １ １ ＯＳ ＣＰＵ ＰｅｎｔｉｕｍⅢ プロセッサ ＷｉｎｄｏｗｓＸＰ 使用した計算機 ＰｅｎｔｉｕｍⅣ プロセッサ Ｒｅｄｈａｔ

Fin