数学の一分野であるグラフ理論において、クリーク和（またはクリーク和）は、2 つのグラフをクリークで接着することにより結合する方法であり、位相幾何学における連結和演算に類似している。2 つのグラフGとHにそれぞれ等しいサイズのクリークがある場合、 GとHのクリーク和は、これらの 2 つのクリークの頂点のペアを識別して 1 つの共有クリークを形成し、次にすべてのクリークのエッジを削除するか（集合和の概念に基づく元の定義）、場合によってはクリークのエッジの一部を削除する（定義の緩和）ことによって、それらの非結合和から形成される。kクリーク和は、両方のクリークがちょうど k 個（または場合によっては最大でk個）の頂点を持つクリーク和である。クリーク和演算を繰り返し適用することにより、3 つ以上のグラフのクリーク和とkクリーク和を形成することもできる。
クリーク和演算においてどの辺を削除すべきかについては、様々な文献で意見が分かれています。弦グラフや絞扼グラフの分解など、文脈によっては辺を削除すべきではありません。一方、グラフを3頂点連結成分に分解するSPQR木分解など、文脈によっては全ての辺を削除すべきです。また、単純グラフのマイナー閉族に対するグラフ構造定理など、文脈によっては、削除する辺の集合を演算の一部として指定することが自然に認められます。
関連概念
クリーク和は木幅と密接な関係がある。2つのグラフの木幅が最大でkであれば、それらのkクリーク和も最大で k である。すべての木は、その辺の 1 クリーク和である。すべての直並列グラフ、あるいはより一般的には木幅が最大で 2 であるすべてのグラフは、三角形の 2 クリーク和として形成される。同様の結果はkのより大きな値にも当てはまる。木幅が最大でkであるすべてのグラフは、最大でk + 1 個の頂点を持つグラフのクリーク和として形成される 。これは必然的にkクリーク和となる。[1]
クリーク和とグラフの連結性の間にも密接な関係があります。グラフが( k + 1)点連結でない場合（つまり、k個の頂点の集合が存在し、その頂点を削除するとグラフが連結されなくなる場合）、そのグラフはより小さなグラフのkクリーク和として表現できます。例えば、 2連結グラフのSPQR木は、そのグラフを3連結成分の2クリーク和として表現したものです。
グラフ構造理論への応用
クリーク和はグラフ構造理論において重要であり、より単純なグラフのクリーク和によって形成されるグラフとして、ある種のグラフ族を特徴付けるために使用される。このタイプの最初の結果[2]は Wagner (1937) の定理であり、5 頂点の完全グラフをマイナーとして持たないグラフは、8 頂点のWagner グラフを持つ平面グラフの 3 クリーク和であることを証明した。この構造定理は、4 色定理がHadwiger 予想のk = 5 の場合と同等であることを示すために使用できる。弦グラフは、エッジを削除せずにクリークのクリーク和によって形成できるグラフであり、絞扼グラフは、エッジを削除せずにクリークと極大平面グラフのクリーク和によって形成できるグラフである。[3]長さが4以上のすべての誘導サイクルがグラフの最小セパレータを形成するグラフ（その削除によりグラフが2つ以上の分離したコンポーネントに分割され、サイクルのサブセットが同じプロパティを持たないグラフ）は、エッジ削除のないクリークと最大平面グラフのクリーク和とまったく同じです。[4] Johnson & McKee (1996) は、弦グラフと直列並列グラフのクリーク和を使用して、正定値完備化を持つ部分行列を特徴付けています。
グラフマイナー演算の下で閉じた任意のグラフ族に対して、クリーク和分解を導くことが可能である。すなわち、すべてのマイナー閉族のグラフは、種数が制限された曲面に「ほぼ埋め込まれた」グラフのクリーク和から形成される。つまり、埋め込みにおいて少数の頂点（他の頂点の任意の部分集合に接続可能な頂点）と渦（曲面埋め込みの面を置き換える、パス幅の狭いグラフ）を省略することができる。 [5]これらの特徴付けは、マイナー閉グラフ族上のNP完全最適化問題に対する近似アルゴリズムと指数時間以下の厳密アルゴリズムの構築において重要なツールとして用いられてきた。 [6]
一般化
クリーク和の理論はグラフからマトロイドへと一般化することもできる。[1]特に、シーモアの分解定理は、正則マトロイド（完全にユニモジュラな行列で表現できるマトロイド）を、グラフィックマトロイド（グラフ内の全域木を表現するマトロイド）、コグラフィックマトロイド、および特定の10要素マトロイドの3つの和として特徴付ける。[1] [7]
注記
- ^ abc Lovász (2006).
- ^ Kříž & Thomas (1990) によれば、グラフ ファミリのクリーク和に基づく特徴付けがさらにいくつか挙げられている。
- ^ シーモア＆ウィーバー（1984年）。
- ^ ディーステル (1987).
- ^ ロバートソン＆シーモア（2003）
- ^ デメインら。 (2004);デメインら。 (2005);デメイン、ハジアガイ、カワラバヤシ (2005)。
- ^ シーモア（1980年）。
参考文献
- エリック・D・ディメイン;フォミン、ヒョードル V.ハジアガイ、モハメッド・タギ。 Thilikos、Dimitrios (2005)、「有界種数グラフおよびHマイナーフリー グラフに関する準指数関数パラメーター化アルゴリズム」、Journal of the ACM、52 (6): 866–893、arXiv : 1104.2230、doi :10.1145/1101821.1101823、MR 2179550、S2CID 6238832。
- Demaine, Erik D. ; Hajiaghayi, MohammedTaghi ; Nishimura, Naomi ; Ragde, Prabhakar ; Thilikos, Dimitrios (2004)「単一交差グラフをマイナーとして除外するグラフのクラスに対する近似アルゴリズム」、Journal of Computer and System Sciences、69 (2): 166– 195、doi :10.1016/j.jcss.2003.12.001、MR 2077379。
- Demaine, Erik D. ; Hajiaghayi, MohammedTaghi; Kawarabayashi, Ken-ichi (2005)、「アルゴリズム的グラフマイナー理論：分解、近似、そして着色」（PDF）、第46回IEEEコンピュータサイエンス基礎シンポジウム論文集（PDF）、pp. 637– 646、doi :10.1109/SFCS.2005.14、ISBN 0-7695-2468-0、S2CID 13238254。
- ディーステル、ラインハルト（1987）、「平面三角形分割の分離特性」、グラフ理論ジャーナル、11（1）：43-52、doi：10.1002/jgt.3190110108、MR 0876203。
- Kříž, Igor; Thomas, Robin (1990)、「クリーク和、木分解、コンパクト性」、離散数学、81 (2): 177– 185、doi : 10.1016/0012-365X(90)90150-G、MR 1054976。
- ジョンソン、チャールズ・R.; マッキー、テリー・A. (1996)、「サイクル完了可能グラフの構造条件」、離散数学、159 ( 1–3 ): 155– 160、doi : 10.1016/0012-365X(95)00107-8、MR 1415290。
- Lovász、László (2006)、「グラフマイナー理論」、米国数学協会紀要、43 (1): 75–86、doi : 10.1090/S0273-0979-05-01088-8、MR 2188176。
- Robertson, N. ; Seymour, PD (2003)、「グラフマイナー XVI. 非平面グラフの除外」、Journal of Combinatorial Theory、シリーズB、89 (1): 43– 76、doi :10.1016/S0095-8956(03)00042-X、MR 1999736。
- シーモア, PD (1980)、「正則マトロイドの分解」、Journal of Combinatorial Theory、シリーズB、28 (3): 305– 359、doi :10.1016/0095-8956(80)90075-1、MR 0579077。
- シーモア, PD ; ウィーバー, RW (1984)、「弦グラフの一般化」、グラフ理論ジャーナル、8 (2): 241– 251、doi :10.1002/jgt.3190080206、MR 0742878。
- Wagner、Klaus (1937)、「Über eine Eigenschaft der ebenen Komplexe」、Mathematische Annalen、114 : 570–590、doi :10.1007/BF01594196、S2CID 123534907。