|
グラフ理論において、木分解とはグラフから木へのマッピングであり、を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。 機械学習では、木分解はjunction tree、clique tree、join treeとも呼ばれ、確率伝搬法や制約充足問題、クエリ最適化、:en:matrix decompositionのような問題で重要な役割を果たす。 木分解の概念は最初ににより導入された。後ににより再発見され、以降他の多数の研究者たちに研究されている。〔 pp.354–355〕 ==定義== 直観的には、木分解は与えられたグラフ''G''の頂点をある一つの木の部分木として表現する。元のグラフ''G''において2つの頂点が隣接するのは対応する部分木が共通部分を持つときに限る。それゆえ、''G''は部分木達の交差グラフの部分グラフをなす。交差グラフそのものはである。 それぞれの部分木はグラフの頂点に木のノードの集合を割り当てる。このことを形式的に定義すると、木のノードひとつひとつを、それに関連付けられたグラフの頂点の集合として表現する。そのため、グラフ''G'' = (''V'', ''E'')が与えられたとき、木分解はペア(''X'', ''T'')である。ここで、''X'' = は''V''の部分集合族で、''T''は頂点が''V''の部分集合''X''''i''であるような木であり、以下の性質を満たす:〔 section 12.3〕 # 全ての集合''X''''i''の和集合は''V''に等しい。つまり、それぞれの頂点は少なくとも一つの木のノードに割り当てられている。 # グラフの各辺(''v'', ''w'') に対して、''v''と''w''の両方を含む部分集合 ''X''''i'' が少なくとも一つ存在する。つまり、グラフの中で頂点が隣接するのは対応する部分木が共通のノードを持つ場合に限られる。 # ''X''''i'' と ''X''''j'' が両方とも頂点''v''を含む場合、''X''''i'' と ''X''''j'' の間の(一意な)パスに含まれる全てのノード''X''''k''も''v''を含む。つまり、''v''に関連付けられたノードたちは''T''の連結な部分集合をなす。これはcoherenceや''running intersection property''としても知られている。これは、「, , がノードで、が から へのパス上にあるならば、である」という条件と同値である。 木分解は一意には定まらない。例えば、自明な木分解として、全ての頂点を含む単一のノードからなる木分解を考えることができる。 台となる木がであるような木分解を道分解と呼ぶ。このような特殊なタイプの木分解から得られる幅のパラメータは道幅として知られている。 木幅''k''の木分解(''X'', ''T'' = (''I'', ''F''))は、とを満たすとき''smooth''であるという。〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「木分解」の詳細全文を読む スポンサード リンク
|