木分解のソースを表示

<!-- https://en.wikipedia.org/w/index.php?title=Tree_decomposition&oldid=648022796  10:46, 20 February 2015‎ --->
{{about|グラフの木構造|グラフの木への分解|Graph_theory#Decomposition_problems}}

[[Image:Tree decomposition.svg|thumb|240px|8点のグラフとそのサイズ6の木分解。グラフの各辺に対して、それがつなぐ2点は木のあるノードに同時に含まれている。グラフの各頂点について、それが含まれているノードは木の連結な部分木をなす。木の各ノードは高々3点しか含まないので、この木分解の木幅は2である。]]

[[グラフ理論]]において、'''木分解'''とは[[グラフ理論|グラフ]]から[[木 (数学)|木]]へのマッピングであり、{{仮リンク| 木幅|en|treewidth}}を定義してグラフの上のある種の計算機科学の問題を高速に解くために使われる。

[[機械学習]]では、木分解は'''junction tree'''、'''clique tree'''、'''join tree'''とも呼ばれ、[[確率伝搬法]]や[[制約充足問題]]、[[クエリ最適化]]、[[:en:matrix decomposition]]のような問題で重要な役割を果たす。

木分解の概念は最初に{{harvs|last=Halin|first=Rudolf|authorlink=Rudolf Halin|year=1976|txt}}により導入された。後に{{harvs|first1=Neil|last1=Robertson|author1-link=Neil Robertson (mathematician)|first2=Paul|last2=Seymour|author2-link=Paul Seymour (mathematician)|year=1984|txt}}により再発見され、以降他の多数の研究者たちに研究されている。<ref>{{harvtxt|Diestel|2005}} pp.354–355</ref>

==定義==
直観的には、木分解は与えられたグラフ''G''の頂点をある一つの木の部分木として表現する。元のグラフ''G''において2つの頂点が隣接するのは対応する部分木が共通部分を持つときに限る。それゆえ、''G''は部分木達の[[交差グラフ]]の[[グラフ理論#部分グラフと拡大グラフ|部分グラフ]]をなす。交差グラフそのものは[[弦グラフ]]である。

それぞれの部分木はグラフの頂点に木のノードの集合を割り当てる。このことを形式的に定義すると、木のノードひとつひとつを、それに関連付けられたグラフの頂点の集合として表現する。そのため、グラフ''G'' = (''V'', ''E'')が与えられたとき、木分解はペア(''X'', ''T'')である。ここで、''X'' = {''X''<sub>1</sub>, ..., ''X''<sub>''n''</sub>} は''V''の部分集合族で、''T''は頂点が''V''の部分集合''X''<sub>''i''</sub>であるような木であり、以下の性質を満たす:<ref>{{harvtxt|Diestel|2005}} section 12.3</ref>

# 全ての集合''X''<sub>''i''</sub>の和集合は''V''に等しい。つまり、それぞれの頂点は少なくとも一つの木のノードに割り当てられている。
# グラフの各辺(''v'', ''w'') に対して、''v''と''w''の両方を含む部分集合 ''X''<sub>''i''</sub> が少なくとも一つ存在する。つまり、グラフの中で頂点が隣接するのは対応する部分木が共通のノードを持つ場合に限られる。
# ''X''<sub>''i''</sub> と ''X''<sub>''j''</sub> が両方とも頂点''v''を含む場合、''X''<sub>''i''</sub> と ''X''<sub>''j''</sub> の間の(一意な)パスに含まれる全てのノード''X''<sub>''k''</sub>も''v''を含む。つまり、''v''に関連付けられたノードたちは''T''の連結な部分集合をなす。これはcoherenceや''running intersection property''としても知られている。これは、「<math>X_i</math>, <math>X_j</math>, <math>X_k</math>がノードで、<math>X_k</math>が<math>X_i</math> から <math>X_j</math>へのパス上にあるならば、<math>X_i \cap X_j \subseteq X_k</math>である」という条件と同値である。

木分解は一意には定まらない。例えば、自明な木分解として、全ての頂点を含む単一のノードからなる木分解を考えることができる。

台となる木が[[道 (グラフ理論)|道グラフ]]であるような木分解を道分解と呼ぶ。このような特殊なタイプの木分解から得られる幅のパラメータは[[道幅]]として知られている。

木幅''k''の木分解(''X'', ''T'' = (''I'', ''F''))は、<math>\forall i \in I : |X_i| = k + 1</math>と<math>\forall (i, j) \in F : |X_i \cap X_j| = k</math>を満たすとき''smooth''であるという。<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref>

==木幅==
{{main|en:Treewidth}}

木分解の''幅''はその最大の集合''X''<sub>''i''</sub>の大きさ引く1である。グラフ''G''の[[木幅]] tw(''G'')はすべての可能な''G''の木分解の幅の最小値である。この定義では、木の木幅を1とするために最大の集合の大きさから1を引いている。木幅は木分解以外の構造からも定義することができる。たとえば[[弦グラフ]]や[[:en:bramble (graph theory)|brambles]]、[[:en:haven (graph theory)|havens]]などである。

与えられたグラフ''G''の木幅が与えられた上限''k''以下であるかどうかを決定する問題は[[NP完全]]である。<ref>{{harvtxt|Arnborg|Corneil|Proskurowski|1987}}.</ref>しかし、''k''が固定された定数である場合、木幅''k''のグラフの認識と、幅''k''の木分解の構成は線型時間で可能である。<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref>時間計算量は''k''については指数関数的に増加する。

==動的計画法==
1970年代の始めに、グラフの上の広い範囲の組合せ最適化問題が、グラフの''次元''(木幅に関係するパラメータ)が制限されている場合には[[動的計画法]]によって効率的に解けることが知られていた。{{sfnp|Bertelé|Brioschi|1972}}その後、多くのNP完全なアルゴリズム的問題が固定された木幅のグラフに対して木分解を用いた動的計画法で効率的に解けることを、1980年代の終わりに数人の研究者が独立に発見した。<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}</ref>

例として、木幅''k''のグラフの[[最大独立集合]]を見つける問題を考える。この問題を解くために、木分解のノードを任意に一つ選んで根とする。木分解のノード''X<sub>i</sub>''に対して、''D<sub>i</sub>''を''X<sub>i</sub>''の下のノード''X<sub>j</sub>''全体の和集合とする。独立集合''S''&nbsp;⊂&nbsp;''X<sub>i</sub>''に対して、''A''(''S'',''i'')を''D<sub>i</sub>''の独立集合''I''であって、
''I''&nbsp;∩&nbsp;''X<sub>i</sub>''&nbsp;=&nbsp;''S''を満たす最大のもののサイズとする。同様に、隣接するノード''X<sub>i</sub>'' , ''X<sub>j</sub>''(''X<sub>j</sub>''の方が根に近い)と独立集合''S''&nbsp;⊂&nbsp;''X<sub>i</sub>''&nbsp;∩&nbsp;''X<sub>j</sub>''に対して、''B''(''S'',''i'',''j'')を''D<sub>i</sub>''の独立集合''I''であって、
''I''&nbsp;∩&nbsp;''X<sub>i</sub>''&nbsp;∩&nbsp;''X<sub>j</sub>''&nbsp;=&nbsp;''S''を満たす最大のもののサイズとする。''A''と''B''は木をボトムアップにたどることによって以下のように計算することができる:
:<math>A(S,i)=|S| + \sum_{j} \left(B(S\cap X_j, j,i) - |S\cap X_j|\right)</math>
:<math>B(S,i,j)=\max_{S'\subset X_i\atop S=S'\cap X_j} A(S',i)</math>
ここで、<math>A(S,i)</math>の式における和は<math>X_i</math>の子ノード全体をわたる。

各ノードと辺において、''A(S,i)''や''B(S,i,j)''を計算すべき集合''S''の個数は高々2<sup>''k''+1</sup>である。そのため、''k''が定数ならば、1ノードおよび1辺あたりの計算は定数時間でできる。最大独立集合の大きさは根のノードに格納されている最大の値であり、最大独立集合自身も(普通の動的計画法のアルゴリズムのように)最大値からバックトラックを行うことで計算できる。そのため、決められた木幅のグラフの最大独立集合問題は線形時間で解ける。類似のアルゴリズムによって、他の多くのグラフの問題を解くことができる。

この動的計画法によるアプローチは、[[機械学習]]において、決められた木幅のグラフにおける[[確率伝搬法]]を行う[[:en:junction tree algorithm]]に用いられる。また木幅を計算し木分解を構成するためにも用いられる。典型的には、そのようなアルゴリズムは最初に木幅を[[近似アルゴリズム|近似]]し、その近似した木幅の木分解を構成し、次にその木分解の上で動的計画法を行うことで正確な木幅を計算する。<ref name="b96"/>

==脚注==
{{Reflist}}

==参考文献==
{{refbegin|colwidth=30em}}
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Corneil | first2 = D. | author2-link = Derek Corneil
 | last3 = Proskurowski | first3 = A.
 | title = Complexity of finding embeddings in a ''k''-tree
 | journal = SIAM Journal on Matrix Analysis and Applications
 | volume = 8 | issue = 2 | year = 1987 | pages = 277–284 | doi = 10.1137/0608024}}. 
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Proskurowski | first2 = A.
 | title = Linear time algorithms for NP-hard problems restricted to partial ''k''-trees
 | journal = Discrete Applied Mathematics
 | volume = 23 | issue = 1 | year = 1989 | pages = 11–24 | doi = 10.1016/0166-218X(89)90031-0}}.
*{{citation
 | last1 = Bern | first1 = M. W.
 | last2 = Lawler | first2 = E. L. | author2-link = Eugene Lawler
 | last3 = Wong | first3 = A. L.
 | title = Linear-time computation of optimal subgraphs of decomposable graphs
 | journal = Journal of Algorithms
 | volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}.
*{{citation
 | last1 = Bertelé | first1 = Umberto
 | last2 = Brioschi | first2 = Francesco
 | title = Nonserial Dynamic Programming
 | year = 1972
 | publisher = Academic Press
 | isbn = 0-12-093450-7}}.
*{{citation
 | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
 | contribution = Dynamic programming on graphs with bounded treewidth
 | title = Proc. 15th International Colloquium on Automata, Languages and Programming
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 317 | year = 1988 | pages = 105–118
 | doi = 10.1007/3-540-19488-6_110}}.
*{{citation
 | last = Bodlaender | first = Hans L. | authorlink = Hans L. Bodlaender
 | title = A linear time algorithm for finding tree-decompositions of small treewidth
 | journal = SIAM Journal on Computing
 | volume = 25 | issue = 6 | year = 1996 | pages = 1305–1317 | doi = 10.1137/S0097539793251219}}.
*{{Citation
| last=Diestel | first=Reinhard
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
| year=2005
| edition=3rd
| isbn=3-540-26182-6
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
}}.
*{{Citation
 | title = ''S''-functions for graphs
 | year = 1976
 | last = Halin | first = Rudolf | authorlink = Rudolf Halin
 | journal = Journal of Geometry
 | pages = 171–186
 | volume = 8
 | doi=10.1007/BF01917434
}}.
*{{citation
 | last1 = Robertson | first1 = Neil | authorlink1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | authorlink2 = Paul Seymour (mathematician)
 | title = Graph minors III: Planar tree-width
 | journal = Journal of Combinatorial Theory, Series B
 | volume = 36
 | issue = 1 | year = 1984 | pages = 49–64
 | doi = 10.1016/0095-8956(84)90013-3}}.
{{refend}}

{{Combin-stub}}
{{DEFAULTSORT:きふんかい}}
[[Category:木 (グラフ理論)]]
[[Category:グラフマイナー理論]]
[[Category:Graph theory objects]]
[[Category:グラフ理論]]
[[Category:数学に関する記事]]