クリークサム

数学の一分野であるグラフ理論において、クリーク和（クリーク和）は、2 つのグラフをクリークで接着することによって結合する方法であり、位相幾何学における連結和演算に類似している。2つのグラフGとHにそれぞれ同じサイズのクリークが含まれる場合、 GとHのクリーク和は、これら 2 つのクリーク内の頂点のペアを識別して 1 つの共有クリーク​​を形成し、次にすべてのクリーク辺を削除するか（集合和の概念に基づく元の定義）、場合によってはクリーク辺の一部を削除する（定義を緩和する）ことによって、それらの非結合和から形成される。kクリーク和は、両方のクリークがちょうどk個（または最大でk個）の頂点を持つクリーク和である。クリーク和演算を繰り返し適用することで、3 つ以上のグラフの クリーク和やkクリーク和を形成することもできる。

クリーク和演算の一部としてどの辺を削除すべきかについては、さまざまな情報源で意見が分かれています。弦グラフや絞殺グラフの分解など、一部のコンテキストでは、辺を削除すべきではありません。グラフを 3 頂点連結コンポーネントにSPQR 木分解するなどの他のコンテキストでは、すべての辺を削除する必要があります。また、単純グラフのマイナー閉族のグラフ構造定理などの他のコンテキストでは、削除する辺のセットを演算の一部として指定できるようにすることが自然です。

クリーク和はツリー幅と密接な関係があります。2 つのグラフのツリー幅が最大でkであれば、それらのkクリーク和も同様です。すべてのツリーは、その辺の 1 クリーク和です。すべての直列並列グラフ、またはより一般的にはツリー幅が最大で 2 であるすべてのグラフは、三角形の 2 クリーク和として形成されます。同じタイプの結果は、kのより大きな値にも適用されます。つまり、ツリー幅が最大でkであるすべてのグラフは、最大でk + 1 個の頂点を持つグラフのクリーク和として形成されます 。これは必然的にkクリーク和になります。^[1]

クリーク和とグラフの接続性の間にも密接な関係があります。グラフが( k  + 1) 頂点接続されていない場合 (つまり、削除するとグラフが切断されるk頂点の集合が存在する場合)、そのグラフはより小さなグラフのkクリーク和として表すことができます。たとえば、 2 連結グラフのSPQR ツリーは、 3 連結コンポーネントの 2 クリーク和としてグラフを表現します。

クリーク和はグラフ構造理論において重要であり、より単純なグラフのクリーク和によって形成されるグラフとして、特定のグラフ族を特徴付けるために使用される。このタイプの最初の結果^[2]は、5頂点の完全グラフをマイナーとして持たないグラフは、8頂点のワグナーグラフを持つ平面グラフの3クリーク和であることを証明したワグナー (1937) の定理であった。この構造定理は、 4色定理がハドヴィガー予想のk  = 5 の場合と同等であることを示すために使用できる。弦グラフは、エッジを削除せずにクリークのクリーク和によって形成できるグラフであり、絞め殺しグラフは、エッジを削除せずにクリークと極大平面グラフのクリーク和によって形成できるグラフである。^{[3]長さが4以上の}誘導サイクルがグラフの最小セパレータを形成するグラフ（その除去によりグラフが2つ以上の分離したコンポーネントに分割され、サイクルのサブセットが同じ特性を持たないグラフ）は、エッジ削除のないクリークと最大平面グラフのクリーク和とまったく同じです。^{[4] Johnson & McKee（1996）は、弦グラフと直列並列グラフのクリーク和を使用して、}正定値完備化を持つ部分行列を特徴付けています。

グラフマイナー演算の下で閉じた任意のグラフ族に対して、クリーク和分解を導くことが可能である。すなわち、すべてのマイナー閉族のグラフは、有界な種数の表面に「ほぼ埋め込まれた」グラフのクリーク和から形成される。つまり、埋め込みでは少数の頂点（他の頂点の任意のサブセットに接続できる頂点）と渦（表面埋め込みの面を置き換えるパス幅の狭いグラフ）を省略できる。 ^[5]これらの特徴付けは、マイナー閉グラフ族上のNP 完全最適化問題に対する近似アルゴリズムと指数時間未満の正確なアルゴリズムの構築において重要なツールとして使用されている。 ^[6]

クリーク和の理論はグラフからマトロイドに一般化することもできる。^[1]特に、シーモアの分解定理は、正則マトロイド（完全にユニモジュラな行列で表現できるマトロイド）を、グラフィックマトロイド（グラフ内の全域木を表すマトロイド）、コグラフィックマトロイド、および特定の10要素マトロイドの3和として特徴付けている。 ^{[1] [7]}