弦グラフ
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/10/05 07:45 UTC 版)
弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、弦とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である(4頂点以上の誘導グラフは閉路を持たないか、弦を持つ)。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、perfect elimination orderingという頂点の順序付けが可能である」「最小頂点分離(minimal separator)(グラフを全域グラフでなくするために除去する必要最小限なグラフ)がクリークである」「木の部分木の交差グラフ」といった特徴も持つ。また、rigid circuit graphs[1]や、triangulated graph[2]とも呼ばれる。
- ^ Dirac (1961)
- ^ Weisstein, Eric W. "Triangulated Graph". MathWorld (英語).
- ^ Fulkerson & Gross (1965).
- ^ Berry, Golumbic & Lipshteyn (2007).
- ^ Bodlaender, Fellows & Warnow (1992).
- ^ Szwarcfiter & Bornstein (1994).
- ^ Maffray (2003).
- ^ 例えば, Agnarsson (2003)のRemark 2.5が有名である。
- ^ Peter Bartlett. “Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations:”. 2019年3月1日閲覧。
- ^ a b Patil (1986)
- ^ Seymour & Weaver (1984).
- ^ Kaplan, Shamir & Tarjan (1999).
- ^ Fomin & Villanger (2013).
- ^ Parra & Scheffler (1997).
- 弦グラフのページへのリンク