任意の誘導閉路の長さが 3 のグラフを弦グラフ（コーダルグラフ, chordal graph）と呼ぶ。弦グラフはその形から、三角化グラフ（triangulated graph）や三角木グラフ、rigit circuit graph とも呼ばれる。この定義は、長さ 4 以上の閉路が必ず弦（コード；閉路の非隣接な2頂点を結ぶ辺）を持つグラフとも言い換えられる。
弦グラフの生成法として、次が知られている。
グラフ \(G\) の誘導部分グラフ \(G_1, G_2, S\) が \(G_1 \cup G_2 = G\) と \(G_1 \cap G_2 = S\) を満たすとき、\(G_1\) と \(G_2\) を \(S\) に沿って貼り合わせて \(G\) が得られるという。
任意の弦グラフ \(G\) がこの手順で生成できることを頂点数の帰納法で示す。弦グラフ \(G\) が完全グラフであれば初期状態で生成されている。そこで完全グラフでない弦グラフ \(G\) が生成できることを示す。完全グラフでなければ隣接しない2頂点 \(a, b\) が存在する。 \(X\) を \(a\) と \(b\) の極小な頂点カット（分離集合）とする。\(C\) を \(a\) を含む \(G-X\) の連結成分とする。 \(G_1 = G[X \cup V(C)]\) 、 \(G_2 = G-C\) は \(G\) の誘導部分グラフであるから、帰納法の仮定より \(G_1, 𝐺_2\) は弦グラフである。従って \(G_1,G_2\) を \(S=G[X]\) に沿って貼り合わせることで \(G\) が得られる。あとは \(S\) が完全グラフであることを示せばよい。完全グラフでなければ、隣接しない2頂点 \(s,t\) が存在。\(s, t\) はどちらも \(a, b\) が属す \(G−X\) の2つの連結成分両方の頂点に隣接する。さもなくば、その頂点を取り除いても \(X\) はなお頂点カットであるから \(X\) の極小性に反する。よって \(G_1,G_2\) 内で \(s, t\) を結ぶ パスがどらちにも存在。そのような2本のパスのうち最短であるものを繋ぐと長さ4以上の誘導閉路になる。これは \(G\) が弦グラフであることに矛盾。従って \(S\) は完全グラフである。
弦グラフは完全消去順という列でも特徴付けられます。頂点 \(v\) の隣接頂点全体 \(N(v)\) がクリークをなすとき、\(v\) を単体的頂点（simplical vertex）と呼ぶことにします。全頂点を並べた列 \((v_1,v_2,\ldots,v_n)\) について、「任意の \(v_i\) が \(G[v_i, v_{i+1}, \ldots, v_{n}]\) で単体的頂点」であるとき、完全消去順（perfect elimination ordering）といいます。
（\(\Leftarrow\)）長さ \(4\) 以上の誘導閉路 \(C\) が存在するとする。\(C\) の頂点のうち、完全消去順において、最初に現れる頂点を \(v\) とする。完全消去順の定義より、\(v\) の隣接頂点を結ぶ弦が存在するので、\(C\) が誘導部分グラフであるという仮定に反する。従って、完全消去順が存在するなら、弦グラフである。
完全消去順は線形時間で求まります。Lexicographic Breadth First Search と Maximum Cardinality Search が知られています。従って、弦グラフの判定は線形時間でできます。
多項式時間で求められること自体は線形時間のアルゴリズムに比べれば簡単に分かります。完全消去順の最後は単体的頂点 \(v\) であれば良いです。単体的頂点の列挙は \(\sum_v d(v)^2 = O(EV)\) でできます。弦グラフの誘導部分グラフもまた弦グラフなので、\(G-v\) に対して、再帰的に単体的頂点を求めれば良く、\(O(EV^2)\) となります。
彩色数
弦グラフは任意の誘導部分グラフ \(H \subseteq G\) が \(\chi(H) = \omega(H)\) を満たすという性質を持っています（\(\chi, \omega\) は彩色数とクリーク数）。この性質を持つグラフを理想グラフと呼びます。弦グラフが理想グラフであることは、
- クリークの貼り合わせで構成できること
- 完全消去順を持つこと
のどちらからでも示せます。１つ目の方法では、貼り合わせるクリークの色を入れ替えて揃えることで、貼り合わせによって彩色数が増加しません。従って、彩色数は初期状態の完全グラフのサイズだけで決まります。２つ目の方法では、完全消去順の降順に貪欲に彩色すると良いです。新たに着色する頂点の隣接頂点のうち、着色済みであるものはクリークをなします。従って、隣接頂点の数が使用済みの色数と等しい場合、新たな色を加えても構いません。
完全消去が線形で求まるので、彩色数も線形で求まります。
Comments