弦グラフ

グラフ理論の数学的分野において、弦グラフとは、4 つ以上の頂点を持つすべてのサイクルが弦を持つグラフのことである。弦とは、サイクルの一部ではないが、サイクルの 2 つの頂点を接続する辺である。同様に、グラフ内のすべての誘導サイクルは、ちょうど 3 つの頂点を持つ必要がある。弦グラフは、完全な消去順序を持つグラフ、各最小セパレータがクリークであるグラフ、およびツリーのサブツリーの交差グラフとして特徴付けられることもある。弦グラフは、リジッド回路グラフ^[1]または 三角形分割グラフ^[2]と呼ばれることもある。グラフの弦完備化は、通常、そのグラフの三角形分割と呼ばれる。

弦グラフは、完全グラフのサブセットです。これらは線形時間で認識でき、グラフの色付けなど他のクラスのグラフでは難しいいくつかの問題は、入力が弦グラフである場合は多項式時間で解決できます。任意のグラフのツリー幅は、それを含む弦グラフの クリークのサイズによって特徴付けられます。

グラフにおける完全消去順序とは、グラフの各頂点vに対して、vと、順序においてv の後に現れるvの隣接頂点がクリークを形成するような順序である。グラフが弦グラフであるためには、完全消去順序を満たす必要がある。^[3]

Rose、Lueker & Tarjan (1976) (Habib et al. 2000 も参照) は、辞書式幅優先探索と呼ばれるアルゴリズムを使用して、弦グラフの完全消去順序を効率的に見つけられることを示している。このアルゴリズムは、グラフの頂点を集合のシーケンスに分割し、最初、このシーケンスはすべての頂点を含む単一の集合で構成される。アルゴリズムは、シーケンス内で以前に選択されていない頂点を含む最も古い集合から頂点v を繰り返し選択し、シーケンスの各集合S を2 つの小さなサブセットに分割する。最初のサブセットはS内のvの隣接頂点で構成され、2 番目は隣接頂点以外の頂点で構成される。この分割プロセスがすべての頂点に対して実行されると、集合のシーケンスには、完全消去順序の逆で、集合ごとに 1 つの頂点が含まれる。

この辞書式幅優先探索プロセスと順序付けが完全消去順序付けであるかどうかをテストするプロセスは両方とも線形時間で実行できるため、弦グラフを線形時間で認識することが可能です。弦グラフ上のグラフサンドイッチ問題はNP完全^[4]ですが、弦グラフ上のプローブグラフ問題は多項式時間の計算量を持ちます。^[5]

弦グラフのすべての完全消去順序の集合は、反マトロイドの基本ワードとしてモデル化できます。Chandran ら (2003) は、この反マトロイドへの接続を、特定の弦グラフのすべての完全消去順序を効率的にリストするためのアルゴリズムの一部として使用しています。

完全消去順序の別の応用は、弦グラフの最大クリークを多項式時間で見つけることですが、一般的なグラフに対する同じ問題はNP 完全です。より一般的には、弦グラフには線形数の最大クリークしか存在できませんが、非弦グラフには指数関数的に多くのクリークが存在する可能性があります。これは、弦グラフのクラスにはクリークがほとんどないことを意味します。弦グラフのすべての最大クリークをリストするには、完全消去順序を見つけ、各頂点vと、完全消去順序でvより後にあるvの隣接頂点に対してクリークを形成し、結果として得られる各クリークが最大かどうかをテストするだけです。

弦グラフのクリークグラフは双対弦グラフである。^[6]

最大の極大クリークは最大クリークであり、弦グラフは完全であるため、このクリークのサイズは弦グラフの彩色数に等しい。弦グラフは完全に順序付け可能であり、完全な消去順序付けの逆の貪欲な色付けアルゴリズムを頂点に適用することで最適な色付けが得られる。 ^[7]

弦グラフの彩色多項式は簡単に計算できます。v 1、v ₂、…、v _{n の順序で完全な消去法を見つけます。N i を、}その順序でv _{i の}後に来るv _iの隣接要素の数とします。たとえば、N _n = 0です。彩色多項式は （最後の因数は単にxなので、当然のことながら、 x は多項式を割り切ります）に等しくなります。明らかに、この計算は弦性に依存しています。^[8]${\displaystyle (x-N_{1})(x-N_{2})\cdots (x-N_{n}).}$

どのようなグラフでも、頂点セパレータとは、その頂点を削除すると残りのグラフが切断される頂点の集合のことです。セパレータが最小となるのは、セパレータでもある適切な部分集合がない場合です。ディラック (1961) の定理によれば、弦グラフとは、各最小セパレータがクリークであるグラフです。ディラックはこの特徴を利用して、弦グラフが完全であることを証明しました。

弦グラフの族は、頂点が 3 つの空でない部分集合A、S、Bに分割できるグラフとして帰納的に定義できます。この場合、⁠ ⁠${\displaystyle A\cup S}$と⁠ ⁠ は${\displaystyle S\cup B}$両方とも弦誘導サブグラフを形成し、Sはクリークであり、AからBへの辺は存在しません。つまり、これらはクリークセパレータによって小さなサブグラフに再帰的に分解されるグラフです。このため、弦グラフは分解可能グラフと呼ばれることもあります。^[9]

Gavril (1974) による弦グラフの別の特徴付けには、ツリーとそのサブツリーが含まれます。

ツリーのサブツリーのコレクションから、サブツリー グラフを定義できます。サブツリー グラフは、サブツリーごとに 1 つの頂点と、ツリーの 1 つ以上のノードで重複する 2 つのサブツリーを接続するエッジを持つ交差グラフです。Gavril は、サブツリー グラフがまさに弦グラフであることを示しました。

弦グラフをサブツリーの交差として表現すると、グラフのツリー分解が形成されます。ツリー幅は、グラフ内の最大クリークのサイズより 1 小さい値になります。任意のグラフGのツリー分解は、このようにして、 Gを弦グラフのサブグラフとして表現したものと見ることができます。グラフのツリー分解は、ジャンクション ツリー アルゴリズムのジャンクション ツリーでもあります。

区間グラフは、パスグラフのサブツリーの交差グラフであり、ツリーの特殊なケースです。したがって、弦グラフのサブファミリーです。

分割グラフは、弦グラフであり、弦グラフの補グラフでもあるグラフです。Bender、Richmond、Wormald (1985) は、 n が無限大に近づくにつれて、分割されたn頂点弦グラフの割合が1 に近づくことを示しました。

プトレマイオスグラフは、弦グラフであり距離遺伝グラフでもあるグラフです。準閾値グラフは、弦グラフでありコグラフでもあるプトレマイオスグラフのサブクラスです。 ブロックグラフは、 2 つの極大クリークが共通する頂点が最大で 1 つであるプトレマイオスグラフの別のサブクラスです。特殊なタイプは風車グラフで、共通頂点はすべてのクリークのペアで同じです。

強く弦のあるグラフとは、弦があり、誘導サブグラフとしてn -sun ( n ≥ 3 )を含まないグラフです。ここで、 n -sun は、Gの ハミルトン閉路の辺に隣接するn頂点の弦グラフGとn次 2 頂点の集合です。

K木は、すべての最大クリークとすべての最大クリークセパレータが同じサイズである弦グラフです。 ^[10] アポロニアンネットワークは弦最大平面グラフ、または同等の平面3木です。 ^[10]最大外平面グラフは2木のサブクラスであるため、弦グラフでもあります。

弦グラフは、よく知られているパーフェクト グラフのサブクラスです。弦グラフのその他のスーパークラスには、弱弦グラフ、cop-win グラフ、奇数ホールフリー グラフ、偶数ホールフリー グラフ、メイニエル グラフなどがあります。弦グラフは、まさに奇数ホールフリーかつ偶数ホールフリーのグラフです (グラフ理論の ホールを参照)。

すべての弦グラフは絞扼グラフ、つまりすべての周辺サイクルが三角形であるグラフである。これは周辺サイクルが誘導サイクルの特別な場合だからである。絞扼グラフは弦グラフと極大平面グラフのクリーク和によって形成できるグラフである。したがって、絞扼グラフには極大平面グラフが含まれる。^[11]

G が任意のグラフである場合、 Gの弦完備化(または最小充填) は、 G をサブグラフとして含む弦グラフです。最小充填のパラメータ化されたバージョンは、固定パラメータで扱いやすく、さらに、パラメータ化された準指数時間で解くことができます。^{[12] [13]} Gのツリー幅 は、このクリークのサイズを最小化するように選択された弦完備化の最大クリークの頂点数より 1 少ないです。 kツリーは、ツリー幅をkよりも大きい数に増やさずに追加のエッジを追加できないグラフです 。したがって、kツリーは独自の弦完備化であり、弦グラフのサブクラスを形成します。弦完備化は、他のいくつかの関連するグラフのクラスを特徴付けるためにも使用できます。^[14]

• Agnarsson, Geir (2003)、「弦グラフとその彩色多項式について」、Mathematica Scandinavica、93 (2): 240–246、doi : 10.7146/math.scand.a-14421、MR  2009583。
• Bender, EA; Richmond, LB; Wormald, NC (1985)、「ほとんどすべての弦グラフは分割される」、J. Austral. Math. Soc.、A、38 (2): 214–221、doi : 10.1017/S1446788700023077、MR  0770128。
• ベルジュ、クロード (1967)、「いくつかの完全グラフのクラス」、ハラリー、フランク(編)、『グラフ理論と理論物理学』、アカデミック プレス、pp. 155–165、MR  0232694。
• ベリー、アン;ゴルンビック、マーティン・チャールズ; リプシュタイン、マリーナ (2007)、「弦プローブグラフとサイクルバイカラーグラフの認識」、SIAM Journal on Discrete Mathematics、21 (3): 573–591、doi :10.1137/050637091。
• Bodlaender, HL ; Fellows, MR ; Warnow, TJ (1992)、「完全な系統発生に対する 2 つの打撃」(PDF)、第 19 回国際オートマトン言語およびプログラミング会議の議事録、コンピュータ サイエンスの講義ノート、第 623 巻、pp. 273–283、doi :10.1007/3-540-55719-9_80、hdl : 1874/16653。
• Chandran, LS; Ibarra, L.; Ruskey, F .; Sawada, J. (2003)、「弦グラフの完全消去順序の列挙と特徴付け」(PDF)、理論計算機科学、307 (2): 303–317、doi :10.1016/S0304-3975(03)00221-4。
• ジョージア州ディラック(1961)、「剛体回路グラフについて」、ハンブルク大学数学セミナー Abhandlungen aus dem Mathematischen der Universität Hamburg、25 (1–2): 71–76、doi :10.1007/BF02992776、MR  0130190、S2CID  120608513。
• Fomin, Fedor V.; Villanger, Yngve (2013)、「最小フィルインのための準指数パラメータ化アルゴリズム」、SIAM J. Comput.、42 (6): 2197–2216、arXiv : 1104.2230、doi :10.1137/11085390X、S2CID  934546。
• フルカーソン, DR ; グロス, OA (1965)、「発生行列と区間グラフ」、パシフィック J. 数学、15 (3): 835–855、doi : 10.2140/pjm.1965.15.835。
• Gavril, Fănică (1974)、「木の部分木の交差グラフはまさに弦グラフである」、Journal of Combinatorial Theory、シリーズ B、16 : 47–56、doi : 10.1016/0095-8956(74)90094-X。
• ゴルビック、マーティン・チャールズ（1980）、アルゴリズムグラフ理論と完全グラフ、アカデミックプレス。
• ハビブ、ミシェル、マッコーネル、ロス、ポール、クリストフ、ヴィエノ、ローラン (2000)、「Lex-BFS とパーティションの改良、推移的方向、区間グラフ認識、連続する 1 のテストへの応用」、理論計算機科学、234 (1–2): 59–84、doi : 10.1016/S0304-3975(97)00241-7。
• Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999)、「Chordal、Strongly Chordal、および Proper Interval Graphs 上のパラメータ化された完了問題の扱いやすさ」、SIAM J. Comput.、28 (5): 1906–1922、doi :10.1137/S0097539796303044。
• Maffray, Frédéric (2003)、「完全グラフの色付けについて」、Reed, Bruce A. ; Sales, Cláudia L. (編)、Recent Advances in Algorithms and Combinatorics、CMS Books in Mathematics、vol. 11、Springer-Verlag、pp. 65–84、doi :10.1007/0-387-22444-0_3、ISBN 0-387-95434-1。
• パラ、アンドレアス; シェフラー、ペトラ (1997)、「弦グラフ埋め込みの特性とアルゴリズム的応用」、離散応用数学、79 (1–3): 171–188、doi : 10.1016/S0166-218X(97)00041-3、MR  1478250。
• パティル、HP (1986)、「 kツリーの構造について」、組合せ論、情報およびシステム科学ジャーナル、11 (2–4): 57–64、MR  0966069。
• ローズ、ドナルド J. (1970 年 12 月)、「三角形グラフと消去プロセス」、数学分析および応用ジャーナル、32 (3): 597–609、doi :10.1016/0022-247x(70)90282-9
• Rose, D.; Lueker, George; Tarjan, Robert E. (1976)、「グラフ上の頂点除去のアルゴリズム的側面」、SIAM Journal on Computing、5 (2): 266–283、doi :10.1137/0205021、MR  0408312。
• シーモア、PD ; ウィーバー、RW (1984)、「弦グラフの一般化」、グラフ理論ジャーナル、8 (2): 241–251、doi :10.1002/jgt.3190080206、MR  0742878。
• Szwarcfiter, JL ; Bornstein, CF (1994)、「弦グラフとパスグラフのクリークグラフ」、SIAM Journal on Discrete Mathematics、7 (2): 331–336、doi :10.1137/s0895480191223191、hdl : 11422/1497。

• グラフクラス包含に関する情報システム: 弦グラフ
• ワイスタイン、エリック・W.「Chordal Graph」。マスワールド。