弦グラフ

弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、弦とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である。 他にも、弦グラフは「単体的頂点  を順に除去することでグラフが除去できる、perfect elimination orderingという頂点の順序付けが可能である」「最小頂点分離がクリークである」「木の部分木の交差グラフ」といった特徴も持つ。また、rigid circuit graphsや、triangulated graphとも呼ばれる。弦グラフは完全グラフの部分グラフである。弦グラフを多項式時間で発見できることもあり、グラフ彩色のようなグラフ一般に対しては困難な問題も、弦グラフに対しては多項式時間で解ける場合もある。グラフの木幅は、それを含む弦グラフのクリークのサイズによって特徴づけられるかも知れない。

1. Perfect elimination とその効率的な導出
--------------------------------

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

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

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

2. 極大クリークとグラフ彩色
---------------

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

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

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

弦グラフの彩色多項式は容易に計算できる。perfect elimination ordering を導出し、//N////i//を//v////i//まで削除した後の//v////i//の次数とする。例えば、最後の頂点に対する//N//である//N////n//、は他の頂点が除去された状態での隣接する頂点の数なので、//N////n// = 0である。彩色多項式はであり、最終項は単に//x//であるため、この多項式は//x//で割り切れる。また、この性質は弦グラフの形から簡単に導ける。

3. 最小頂点分離
---------

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

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

4. 部分木の交差グラフ
------------

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

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

5. 他のグラフとの関連
------------

5.1. 特別な弦グラフ
------------

区間グラフは道の部分木の交差グラフであり、木の特殊な場合である。したがって、弦グラフの一種である。
スプリットグラフは、あるグラフと、その補グラフがともに弦グラフであるようなグラフである。頂点数//n//が増加するにつれ、弦グラフがスプリットグラフである割合は1に近づくBender.
プトレマイオスグラフは、弦グラフの内、Distance-hereditary graphでもあるものをいう。Distance-hereditary graphとは、2頂点間の距離が、その2頂点を含む任意の連結な誘導部分グラフにおいても変化しないグラフである。
準閾値グラフはプトレマイオスグラフの一種であり、弦グラフであり、cographであるプトレマイオスグラフをいう。
ブロックグラフもプトレマイオスグラフの一種であり、任意の2つの極大クリークが少なくとも1つの頂点を共有するようなグラフである。
風車グラフはさらにそのブロックグラフの特殊な例であり、任意の2つの極大クリークの共有頂点がある1つの頂点であるようなグラフである。
強弦グラフは//n//-sun グラフを誘導部分グラフとして持たない弦グラフである。ここで、 //n//-sun グラフとは、2//n//頂点からなるハミルトン閉路に、奇数個離れた頂点をつなぐ弦が1個しか含まれないないグラフである。頂点集合内には隣接する頂点が1組ずつしかないような2つの頂点集合に分けられるグラフでもある。
//K//-木は全ての極大クリークと極大クリーク分離が同じサイズの弦グラフである。
アポロニアンネットワークは、弦グラフである極大平面グラフもしくは平面グラフである3-木である。
極大外平面グラフは2-木のサブクラスであり、そのため弦グラフである。

5.2. 弦グラフを含むグラフ
---------------

弦グラフは、パーフェクトグラフの一種である。 また、弦グラフは、弱弦グラフ、コップウィングラフ、odd-hole-free graphs、even-hole-free graph、Meyniel graphなどの特殊な場合でもある。 弦グラフは、odd-hole-free graphsでもeven-hole-free graphでもあるグラフである。

弦グラフは、strangulated graphStrangulated graphsは極大平面グラフと弦グラフのクリーク和で形成される。それゆえに、strangulated graphは極大平面グラフを含むSeymour。

6. 弦化と木幅
----------------------------

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

7. 脚注
-----

8. 参考文献
-------

last = Agnarsson .
last1 = Bender .
last1 = Berry .
last1 = Bodlaender .
last1 = Chandran .
last = Dirac .
last1 = Fomin .
last1 = Fulkerson .
last = Gavril .
first=Martin Charles.
last1 = Habib .
last1 = Kaplan .
last = Maffray .
last1 = Parra .
last = Patil .
last1 = Rose .
last1 = Seymour .
last1 = Szwarcfiter .

9. 外部リンク
--------

[1]: [2]