グラフをC-三角化するアルゴリズム

概要

論文の詳細を見る
本文では自己ループや多重辺のないグラフ,すなわち単純グラフG=(V,E)扱い,単にグラフと呼ぶ.ここでVはGの点集合であり,Eは辺集合である.n=|V|は点の個数,m=|E|は辺の本数である.与えられたグラフGがk色で点彩色されているとし,その彩色をc:V→{1,2,・・・,k}とする時,次の条件(a)及び(b)を満たすグラフG7=(V',E'),V'=V,E⊆E'をグラフGのc-三角化という.(a)グラフG_Tの,任意の4点以上からなる点誘導部分グラフは閉路でない(b)cはグラフG_Tの点彩色である.本文では,cがグラフGの3色による点彩色である時のc-三角化を考える.Gが3色で点彩色されている時,Gをc-三角化するO(α(n)・n)時間アルゴリズムが知られている.ここでα(n)はアッカーマン関数の逆関数である.本文ではO(n)時間アルゴリズムを与える.グラフのc-三角化は以下のような系統木推定問題に応用できる.入力は種類の(生物)種及び各(生物)種の特徴である.種はk個の特徴項目αについてそれぞれ特徴α_iを持っているとする.各特徴α_iはいくつかの種で共通であるかもしれない.この時,これらの種の系統木(図2)を推定して出力するのが系統木推定問題である.ただし,系統木において点は種に対応する.葉点は入力の種に対応し,内点は入力の種または推定された種に対応する.推定された種については各特徴項目の特徴が推定される.また共通の特徴を持つ種は系統木上で1つの部分木を構成するものとする,なお,このような系統木が常に存在するとは限らない.この問題を解くために,次のようなグラフGを作成する(図3).Gの点は各特徴α_1,α_2,・・・,β_1,β_2,・・・,γ_1,γ_2,・・・に対応する.特徴α_i,β_jを持つ種が存在する時,かつその時に限りGに辺α_iβ_j角を付け加える.Gの各クリークはクリークに含まれる点に対応する特徴を全て持つ種に対応する.Gのクリークは高々k点からなる.ここでGのクリークとはGの極大完全部分グラフのことである.α_1,α_2,・・・を同じ色,β_1,β_2,・・・を同じ色γ_1,γ_2,・・・を同じ色とみなすと,グラフGは3色で彩色されている.この彩色をcとする.系統木が存在する必要十分条件は,Gのc-三角化グラフG_rが存在することである.G_rが存在するときはG_rから系統木が構成できる.系統木が存在するにもかかわらずG_rが存在しないと仮定すると,点彩色の条件を壊すことなくGに辺を任意本数追加したグラフG'_rには必ず閉路υ_1υ_2・・・,υ_rυ_1を誘導するr≥4点の点集合S={υ_1υ_2,・・・,υ_r}が存在する.系統木でυ_1υ_2,・・・υ_rはそれぞれ部分木Τ_1Τ_2・・・,Τ_rに対応する.Τ_1はΤ_2Τ_rと共通点を持つが,Τ_3,・・・,Τ_<r-1>とは共通点を持たない.Τ_rはΤ_1,Τ_<r-1>と共通点を持つがΤ_2,・・・,Τ_<r-2>とは共通点を持たない.同様に2≤i≤r-1なるはΤ_iはΤ_<i+1>,Τ_<i-1>とのみ共通点を持つ.このときG'_Tに対応する系続木に閉路が存在することになり矛盾する.GからG_Tを作る時に新たに追加された辺は,種の存在を推定することに相当する.図3でGは実線で,G_Tは実線と点線で描かれている.[&figure][&figure][&figure]
1992-09-28

グラフをC-三角化するアルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク