部分木の交差グラフ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/05 07:45 UTC 版)
1974年、Gavrilによって、部分木を用いた弦グラフの異なる定義が用いられた。 木の部分木の集合から、部分木ごとに1つの頂点と重複する2つの部分木を持つ交差グラフである「部分木グラフ」を定義できる。この「部分木グラフ」は弦グラフであることをGavrilは証明した。 部分木の交差として弦グラフを表すと、グラフの木幅がグラフ内の最大クリークのサイズより1小さい、木分解が生成される。任意のグラフG の木分解は弦グラフの部分グラフとしてGを表現したものとして捉えられる。グラフの木分解は、Junction tree algorithmの木分解でもある。
※この「部分木の交差グラフ」の解説は、「弦グラフ」の解説の一部です。
「部分木の交差グラフ」を含む「弦グラフ」の記事については、「弦グラフ」の概要を参照ください。
ウィキペディア小見出し辞書の「部分木の交差グラフ」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 部分木の交差グラフのページへのリンク
