弦グラフ

弦グラフについて

弦グラフは、グラフ理論において特定の構造を持つグラフの一種です。具体的には、内部に存在する長さ4以上の閉路すべてが弦を持つ特徴があります。ここで言う弦とは、特定の閉路の二頂点を結ぶ辺であり、その閉路自体には含まれません。また、弦グラフは誘導閉路グラフとの関係もあり、常に3頂点の閉路を含むことと同値です。具体的には、長さ4以上の誘導グラフは閉路を含まないか、弦を持つとされています。

弦グラフにはいくつかの興味深い特性があります。例えば、弦グラフは「完璧な消去順序 (perfect elimination ordering)」を持つことができます。これは、隣接頂点がクリークを形成するグラフにおいて、ある頂点を順に削除していくことで、グラフ全体を効率的に削除できる順序です。この消去順序は、グラフが弦グラフである場合に限り存在します。

また、弦グラフは最小頂点分離がクリークであるという特性を持ちます。これは、弦グラフがパーフェクトなグラフであることの証明にも用いられる重要な性質です。弦グラフは、特定の条件を満たす頂点集合に再帰的に分解できるため、分解可能なグラフ（decomposable graphs）とも称されています。

完璧な消去の導出法

弦グラフの特性の中で特に注目すべき点は、完璧な消去順序 (perfect elimination ordering) の効率的な導出です。Rose, Lueker & Tarjan (1976)が提案した「辞書順探索 (Lexicographic Breadth First Search)」というアルゴリズムを用いることで、弦グラフの完璧な消去順序を効果的に見つけることが可能です。この手法では、全ての頂点を含む集合から隣接点によって順次分割し、最終的な出力順序は完璧な消去順序の逆順となります。この処理は線形時間で行えるため、弦グラフに対する複数の問題を効率的に評価できます。

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

弦グラフにおける最大クリーク問題に対しても、完璧な消去順序を活用することができます。一般のグラフにおいて最大クリークの決定はNP完全問題ですが、弦グラフでは効率的に解決可能です。弦グラフは、頂点数に対して比例する数の極大クリークを持つことができ、クリークが極大であるかを簡単に判別できます。

また、弦グラフがパーフェクトである場合、その極大クリークは最大クリークにもなります。これにより、グラフの彩色数と極大クリークのサイズが一致するという特性も成り立ちます。弦グラフの彩色多項式は簡単に計算でき、グラフの特徴を引き立てます。

最小頂点分離と交差グラフ

弦グラフにおける最小頂点分離の特性は、クリークの存在から導かれます。最小頂点分離によって形成されるグラフは、より小さな部分的なクリークによって再帰的に分割され、これにより弦グラフの性質が観察されます。

Gavrilによって1974年に示された「部分木の交差グラフ」は、弦グラフの一つの定義として広く認識されています。この定義から、グラフ内の最大クリークのサイズと木幅に対する新しい見解が得られ、木分解の性質とも関連があります。

まとめ

弦グラフは最大クリーク問題やグラフ彩色、最小頂点分離など、さまざまな重要な問題に対する強力な道具です。これらの特性は、弦グラフがグラフ理論において中心的な役割を果たす理由の一つです。また、弦グラフは他のグラフとも密接に関連しており、様々な応用の可能性を秘めています。

もう一度検索