クリーク（グラフ理論）

グラフ理論において、クリーク( / ˈ k l iː k /または/ ˈ k l ɪ k / ) は、無向グラフの頂点のサブセットであり、クリーク内のすべての異なる 2 つの頂点は隣接しています。つまり、グラフのクリークは完全なの誘導サブグラフです。クリークはグラフ理論の基本概念の 1 つであり、他の多くの数学の問題やグラフの構築に使用されます。クリークはコンピューター サイエンスでも研究されてきました。グラフ内に特定のサイズのクリークがあるかどうかを見つけるタスク(クリーク問題)はNP 完全ですが、この困難な結果にもかかわらず、クリークを見つけるための多くのアルゴリズムが研究されてきました。 ${\displaystyle G}$${\displaystyle G}$

完全サブグラフの研究は、少なくともエルデシュとシェケレス（1935）によるラムゼー理論のグラフ理論的再定式化にまで遡りますが、 ^[1]クリークという用語は、ソーシャルネットワークの完全サブグラフを使用して人々のクリーク、つまりお互いを知っている人々のグループをモデル化したルースとペリー（1949）に由来しています。クリークは、科学、特にバイオインフォマティクスの分野で他の多くの用途があります。

無向グラフG = ( V , E )内のクリークCは、すべての 2 つの異なる頂点が隣接しているような頂点C ⊆ Vの部分集合です。これは、 Cによって誘導されるGの誘導サブグラフが完全グラフであるという条件に相当します。場合によっては、クリークという用語はサブグラフを直接指すこともあります。

最大クリークは、隣接する頂点を 1 つ追加することによって拡張できないクリーク、つまり、より大きなクリークの頂点セット内に排他的に存在しないクリークです。一部の著者は、クリークが最大であることを要求する方法でクリークを定義し、最大ではない完全なサブグラフに対して他の用語を使用します。

グラフGの最大クリークとは、それ以上の頂点を持つクリークが存在しないクリークのことである。また、グラフGのクリーク数ω ( G )は、 G内の最大クリークの頂点数である。

Gの交差数は、Gのすべての辺をカバーするクリークの最小数です。

グラフGのクリーク被覆数とは、その和がグラフの 頂点集合Vを覆うGのクリークの最小の数です。

グラフの最大クリーク横断は、グラフの各最大クリークに少なくとも1つの頂点が含まれるという性質を持つ頂点のサブセットです。^[2]

クリークの反対は独立集合であり、すべてのクリークは補グラフ内の独立集合に対応します。クリークカバー問題は、グラフ内のすべての頂点を含むクリークをできるだけ少なく見つけることに関するものです。

関連する概念として、完全な二部サブグラフであるバイクリークがあります。グラフの二部次元は、グラフのすべての辺をカバーするために必要なバイクリークの最小数です。

クリークに関する数学的な結果は次のとおりです。

• トゥランの定理は、密なグラフにおけるクリークのサイズの下限値を与える。^[3]グラフに十分な数の辺がある場合、必ず大きなクリークが含まれる。例えば、頂点が 個、辺が 個以上の グラフには、必ず 3 頂点クリークが含まれる。${\displaystyle n}$${\displaystyle \scriptstyle \left\lfloor {\frac {n}{2}}\right\rfloor \cdot \left\lceil {\frac {n}{2}}\right\rceil }$
• ラムゼーの定理は、すべてのグラフまたはその補グラフには、少なくとも対数個の頂点を持つクリークが含まれていることを述べています。^[4]
• Moon & Moser (1965) の結果によると、3 n 個の頂点を持つグラフには最大 3 ^{n 個}の最大クリークが存在する可能性があります。この制限を満たすグラフは、Moon–Moser グラフK _3,3,...であり、これは Turán の定理の極限ケースとして生じるTurán グラフの特殊なケースです。
• ハドヴィガー予想は、まだ証明されていないが、グラフ内の最大のクリークマイナーの大きさ（ハドヴィガー数）とその彩色数を関連付けるものである。
• Erdős -Faber-Lovász 予想は、グラフの色をクリークに関連付けます。
• エルデシュ・ハイナル予想は、禁制グラフ特性によって定義されたグラフの族には、大きなクリークまたは大きなコクリークのいずれかが存在するというものです。

いくつかの重要なグラフのクラスは、そのクリークによって定義または特徴付けられます。

• クラスターグラフは、接続されたコンポーネントがクリークであるグラフです。
• ブロックグラフは、 2 重連結コンポーネントがクリークであるグラフです。
• 弦グラフは、頂点を完全消去順序、つまり順序​​付けにおいて各頂点vより後に来る各頂点vの隣接頂点がクリークを形成するような順序付けに順序付けできるグラフです。
• コグラフとは、その誘導サブグラフのすべてが、任意の最大クリークが単一の頂点で任意の最大独立集合と交差するという特性を持つグラフです。
• 区間グラフは、各頂点vに対して、 vを含むクリークが順序付けにおいて連続するように最大クリークを順序付けできるグラフです。
• 線グラフは、各頂点がカバー内の 2 つのクリークに正確に属するように、エッジがエッジ分離クリークによってカバーされるグラフです。
• 完全グラフとは、すべての誘導部分グラフにおいてクリーク数が彩色数と等しいグラフです。
• 分割グラフとは、あるクリークにすべてのエッジの少なくとも 1 つのエンドポイントが含まれるグラフです。
• 三角形のないグラフは、頂点と辺以外のクリークを持たないグラフです。

さらに、他の多くの数学的構成にはグラフのクリークが関係している。その中には、

• グラフGのクリーク複体は、G内のすべてのクリークに対して単体を持つ抽象単体複体X ( G )である。
• 単体グラフは、グラフGのすべてのクリークを頂点とし、頂点が 1 つだけ異なる 2 つのクリークを辺で結ぶ無向グラフ κ( G ) である。これはメディアングラフの一例であり、グラフのクリークに関するメディアン代数と関連している。3 つのクリークA、B、Cのメディアンm ( A、B、C ) は、クリークの頂点がクリークA、B、Cのうち少なくとも 2 つに属するクリークである。^[5]
• クリーク和は、共有クリーク​​に沿って 2 つのグラフをマージして結合する方法です。
• クリーク幅は、非結合の和集合、ラベル付け操作、および指定されたラベルを持つすべての頂点のペアを接続する操作からグラフを構築するために必要な、異なる頂点ラベルの最小数の観点から見たグラフの複雑さの概念です。クリーク幅が 1 のグラフは、まさにクリークの非結合の和集合です。
• グラフの交差数は、グラフのすべてのエッジをカバーするために必要なクリークの最小数です。
• グラフのクリーク グラフは、その最大クリークの交差グラフです。

完全部分グラフに密接に関連する概念は、完全グラフの細分と完全グラフマイナーです。特に、クラトフスキーの定理とワグナーの定理は、それぞれ禁制の完全および完全二部細分とマイナーによって平面グラフを特徴付けます。

コンピュータサイエンスにおいて、クリーク問題とは、与えられたグラフ内で最大のクリーク、またはすべてのクリークを見つける計算問題である。これはNP完全であり、Karpの21のNP完全問題のうちの1つである。^[6]また、固定パラメータでは扱いにくく、近似するのが難しい。しかし、クリークを計算するためのアルゴリズムは数多く開発されており、指数時間で実行されるもの（ Bron-Kerboschアルゴリズムなど）や、問題が多項式時間で解ける平面グラフや完全グラフなどのグラフ族に特化したものなどがある。

グラフ理論における「クリーク」という言葉は、Luce と Perry (1949) の研究から生まれたもので、彼らは完全なサブグラフを使用してソーシャル ネットワーク内のクリーク(お互いを知っている人々のグループ)をモデル化しました。同じ定義は、Festinger (1949) によって、あまり専門用語を使わない記事で使用されました。どちらの研究も、マトリックスを使用してソーシャル ネットワーク内のクリークを発見することを扱っています。ソーシャル クリークをグラフ理論的にモデル化する継続的な取り組みについては、Alba (1973)、Peay (1974)、Doreian と Woodard (1994) を参照してください。

バイオインフォマティクスのさまざまな問題が、クリークを使用してモデル化されてきました。たとえば、Ben-Dor、Shamir & Yakhini (1999 ) は、遺伝子発現データのクラスタリングの問題を、データを表すグラフをクリークの非結合和として形成されたグラフに変換するために必要な変更の最小数を見つける問題としてモデル化しています。Tanay、Sharan & Shamir (2002) は、クラスターがクリークである必要がある発現データに対する同様のバイクラスタリング問題について説明しています。Sugihara (1984) は、クリークを使用して食物網の生態学的地位をモデル化しています。Day & Sankoff (1986) は、進化樹を推測する問題を、種の特徴を頂点とするグラフで最大のクリークを見つける問題として説明しています。2 つの特徴を組み合わせた完全な系統樹が存在する場合、2 つの頂点は辺を共有します。 Samudrala と Moult (1998) は、タンパク質構造予測を、頂点がタンパク質のサブユニットの位置を表すグラフ内のクリークを探す問題としてモデル化しました。また、Spirin と Mirny (2003) は、タンパク質間相互作用ネットワーク内のクリークを探すことで、互いに密接に相互作用し、クラスター外のタンパク質との相互作用がほとんどないタンパク質のクラスターを発見しました。パワー グラフ分析は、複雑な生物学的ネットワーク内のクリークと関連構造を見つけることで、これらのネットワークを単純化する方法です。

電気工学では、Prihar (1956) はクリークを通信ネットワークの解析に使用し、Paull & Unger (1959) はクリークを部分的に指定されたブール関数を計算するための効率的な回路の設計に使用しています。クリークは自動テストパターン生成にも使用されており、可能性のある障害の非互換性グラフ内の大きなクリークは、テストセットのサイズの下限を提供します。^[7] Cong & Smith (1993) は、電子回路をより小さなサブユニットに階層的に分割するためのクリークの応用について説明しています。

化学では、Rhodes ら (2003) はクリークを使用して、ターゲット構造と高い類似性を持つ化学データベース内の化学物質を記述します。Kuhl、Crippen、Friesen (1983) はクリークを使用して、2 つの化学物質が互いに結合する位置をモデル化します。

• 派閥ゲーム

• ワイスタイン、エリック W.、「クリーク」、MathWorld
• ワイスシュタイン、エリック W.、「クリーク数」、MathWorld