弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、閉路の弦とは、その閉路自体には含まれず、かつ、その閉路を構成する2頂点を両端点とする辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である（4頂点以上の誘導グラフは閉路を持たないか、弦を持つ）。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、perfect elimination orderingという頂点の順序付けが可能である」「最小頂点分離(minimal separator)（グラフを全域グラフでなくするために除去する必要最小限なグラフ）がクリークである」「木の部分木の交差グラフ（英語版）」といった特徴も持つ。また、rigid circuit graphs^[1]や、triangulated graph^[2]とも呼ばれる。

弦グラフは完全グラフの部分グラフである。弦グラフを多項式時間で発見できることもあり、グラフ彩色のようなグラフ一般に対しては困難な問題も、弦グラフに対しては多項式時間で解ける場合もある。グラフの木幅(treewidth)は、それを含む弦グラフのクリークのサイズによって特徴づけられるかも知れない。

Perfect elimination とその効率的な導出

perfect elimination orderingとは、「隣接する頂点集合がクリークを形成しているグラフの頂点 v の削除」を繰り返し、グラフ全体が削除されるような順序付けである。グラフが弦グラフであれば、そしてその時に限りグラフはperfect elimination orderingを持つ^[3]。

Rose, Lueker & Tarjan (1976) (see also Habib et al. 2000) は、Lexicographic Breadth First Search と呼ばれる辞書順に並べながら探索する手法で、効率的に弦グラフのperfect elimination orderingが見つかると示した。このアルゴリズムは、グラフの頂点を集合列に以下の手法で分割する。 まず、全ての頂点を含む1つの集合を考える。そして、一度も選ばれていない頂点を含む最初の集合 S から頂点 v を選び、S を「v に隣接している頂点」と「v に隣接していない頂点」の2つの集合に分割する。この分割を繰り返し、全ての頂点を一度ずつ選び終わったとき、perfect elimination orderingの逆の順に並ぶ。

lexicographic breadth first searchと、出力された順序がperfect elimination orderingかを確かめる処理は両方とも線形時間であるため、弦グラフに対して線形時間で処理可能である。弦グラフに対するprobe graph problemは多項式時間で解ける^[4]一方、弦グラフに対するGraph sandwich problemはNP完全である^[5]。

弦グラフに対する全てのperfect elimination ordering集合は反マトロイド(antimatroid)の基としてモデル化できる。例えば、Chandran et al. (2003)は与えられた弦グラフの全てのperfect elimination orderingsを効率的に列挙するアルゴリズムの一部として、反マトロイドへのこの接続を使いた。

極大クリークとグラフ彩色

perfect elimination orderingは、多項式時間で弦グラフの最大クリーク問題にも応用できる。最大クリーク問題は一般のグラフに対してはNP完全である。より一般には、弦グラフは極大クリークを高々頂点数に対して比例する数だけ持ちうるが、一般のグラフに対しては頂点数に対して極大クリークの個数は指数関数的に増大する。弦グラフの極大クリークを列挙するには、perfect elimination orderingを見つけ、その除去で用いるクリークが極大であるかを判定するだけである。

弦グラフのクリークは、双対弦グラフ（英語版）と呼ばれる^[6]。

弦グラフがパーフェクトであるとき、極大クリークが最大クリークとなる。この時、クリークの頂点数はグラフの彩色数（頂点彩色）と等しくなる。また、弦グラフはperfect elimination orderingの逆順に頂点を選択して、貪欲法を用いることで最適な彩色が可能である^[7]。

弦グラフの彩色多項式（英語版）は容易に計算できる。perfect elimination ordering ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$を導出し、N_iをv_iまで削除した後のv_iの次数（隣接する頂点数）とする。例えば、最後の頂点に対するNであるN_n、は他の頂点が除去された状態での隣接する頂点の数なので、N_n = 0である。彩色多項式は${\displaystyle (x-N_{1})(x-N_{2})\cdots (x-N_{n})}$であり、最終項は単にxであるため、この多項式はxで割り切れる。また、この性質は弦グラフの形から簡単に導ける。^[8]

最小頂点分離

弦グラフに限らず、頂点分離（英語版）（vertex separator）とは、それらを除去すると残されたグラフが非連結となるような頂点集合を指す。最小頂点分離とは、頂点分離の部分集合が頂点分離とならない場合、その頂点分離を最小頂点分離と呼ぶ。弦グラフの頂点分離はクリークでありDirac (1961)、この性質は弦グラフがパーフェクトグラフである証明に使われた。

弦グラフの族は、A∪SとS∪Bは弦グラフである誘導部分グラフであり、Sはクリークであり、そしてA と B 間に辺が存在しないという3つを満たす、空集合ではない頂点集合A、S、Bに分割できるグラフとして再帰的に定義できる。つまり、クリークによって小さな部分グラフに再帰的に分解されるグラフである。このため、弦グラフは decomposable graphsとも呼ばれていた^[9]。

部分木の交差グラフ

1974年、Gavrilによって、部分木を用いた弦グラフの異なる定義が用いられた。

木の部分木の集合から、部分木ごとに1つの頂点と重複する2つの部分木を持つ交差グラフである「部分木グラフ」を定義できる。この「部分木グラフ」は弦グラフであることをGavrilは証明した。

部分木の交差として弦グラフを表すと、グラフの木幅がグラフ内の最大クリークのサイズより1小さい、木分解が生成される。任意のグラフG の木分解は弦グラフの部分グラフとしてGを表現したものとして捉えられる。グラフの木分解は、Junction tree algorithmの木分解でもある。

他のグラフとの関連

弦化(Chordal completion)と木幅

任意のグラフGの弦化とは、Gを部分グラフとして持つような弦グラフである。最小弦化は複数のパラメータに従う計算複雑性を持ち、準指数時間で解くことができる^[12][13]。 Gの木幅はクリークのサイズが最小となるような弦化が施されたGの最大クリークの頂点数-1である。 k-木は木幅をkより大きくしなければ辺を追加できないグラフである。したがって、k-木はそれ自身の弦化であり、弦グラフの一種である。弦化は他のグラフの特徴付にも使われる^[14]。

脚注

参考文献

• Agnarsson, Geir (2003), “On chordal graphs and their chromatic polynomials”, Mathematica Scandinavica 93 (2): 240–246, MR2009583, http://www.mscand.dk/article/view/14421 .
• Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), “Almost all chordal graphs split”, J. Austral. Math. Soc., A 38 (2): 214–221, doi:10.1017/S1446788700023077, MR0770128 .
• Berry, Anne; Golumbic, Martin Charles; Lipshteyn, Marina (2007), “Recognizing chordal probe graphs and cycle-bicolorable graphs”, SIAM Journal on Discrete Mathematics 21 (3): 573–591, doi:10.1137/050637091 .
• Bodlaender, H. L.; Fellows, M. R.; Warnow, T. J. (1992), “Two strikes against perfect phylogeny”, Proc. of 19th International Colloquium on Automata Languages and Programming, Lecture Notes in Computer Science, 623, pp. 273–283, doi:10.1007/3-540-55719-9_80 .
• Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003), “Enumerating and characterizing the perfect elimination orderings of a chordal graph”, Theoretical Computer Science 307 (2): 303–317, doi:10.1016/S0304-3975(03)00221-4, http://www.cis.uoguelph.ca/~sawada/papers/chordal.pdf .
• Dirac, G. A. (1961), “On rigid circuit graphs”, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 25: 71–76, doi:10.1007/BF02992776, MR0130190 .
• Fomin, Fedor V.; Villanger, Yngve (2013), “Subexponential Parameterized Algorithm for Minimum Fill-In”, SIAM J. Comput. 6: 2197–2216, arXiv:1104.2230, doi:10.1137/11085390X .
• Fulkerson, D. R.; Gross, O. A. (1965), “Incidence matrices and interval graphs”, Pacific J. Math. 15: 835–855, doi:10.2140/pjm.1965.15.835, http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572 .
• Gavril, Fănică (1974), “The intersection graphs of subtrees in trees are exactly the chordal graphs”, Journal of Combinatorial Theory, Series B 16: 47–56, doi:10.1016/0095-8956(74)90094-X .
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press .
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), “Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing”, Theoretical Computer Science 234: 59–84, doi:10.1016/S0304-3975(97)00241-7, http://www.cs.colostate.edu/~rmm/lexbfs.ps .
• Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), “Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs”, SIAM J. Comput. 5: 1906–1922, doi:10.1137/S0097539796303044 .
• Maffray, Frédéric (2003), “On the coloration of perfect graphs”, in Reed, Bruce A.; Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1 .
• Parra, Andreas; Scheffler, Petra (1997), “Characterizations and algorithmic applications of chordal graph embeddings”, Discrete Applied Mathematics 79 (1-3): 171–188, doi:10.1016/S0166-218X(97)00041-3, MR1478250 .
• Patil, H. P. (1986), “On the structure of k-trees”, Journal of Combinatorics, Information and System Sciences 11 (2–4): 57–64, MR966069 .
• Rose, D.; Lueker, George; Tarjan, Robert E. (1976), “Algorithmic aspects of vertex elimination on graphs”, SIAM Journal on Computing 5 (2): 266–283, doi:10.1137/0205021 .
• Seymour, P. D.; Weaver, R. W. (1984), “A generalization of chordal graphs”, Journal of Graph Theory 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR742878 .
• Szwarcfiter, J.L.; Bornstein, C.F. (1994), “Clique graphs of chordal and path graphs”, SIAM Journal on Discrete Mathematics 7: 331–336, doi:10.1137/s0895480191223191 .

外部リンク

• Information System on Graph Class Inclusions: chordal graph
• Weisstein, Eric W. "Chordal Graph". mathworld.wolfram.com (英語).