弦グラフ 弦グラフの概要

ウィキペディア

弦グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/05 07:45 UTC 版)

閉路（黒）と2本の弦（緑）で構成された、弦グラフの例。どちらかの弦を削除すると、弦を持たない長さ4の閉路が生まれるため、弦グラフではなくなる。

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

Perfect elimination とその効率的な導出

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

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は多項式時間で解ける一方、弦グラフに対するGraph sandwich problemはNP完全である。

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

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

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

弦グラフのクリークは、双対弦グラフと呼ばれる。

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

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