Loading AI tools
ウィキペディアから
グラフ理論において、無向グラフ のクリーク(英: clique)とは、頂点の部分集合 のうち、 に属するあらゆる2つの頂点を繋ぐ辺が存在するものをいう。これはすなわち、 から誘導される部分グラフが完全だということである。なお、頂点の集合ではなく、そのような部分グラフをクリークと呼ぶこともある。(また包含関係に関して極大な完全部分グラフのみをクリークと呼ぶこともあるので注意がいる[1]。)クリークに属する頂点数をそのクリークの大きさと言う。
この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年5月) 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
与えられたグラフに指定された大きさのクリークがあるかどうかを求める問題(クリーク問題、その特殊版が最大クリーク問題)はNP完全である。
クリークの逆の概念を独立集合と呼び、クリークは必ず補グラフの独立集合と対応する。
この用語は、頂点を人、辺を「知っている」という意味としたとき、全ての人が互いに知っていることになるため "clique"(徒党、派閥)と名付けられた。
グラフ の最大クリークは理論上重要であり、 で表される。[2]
グラフ の部分グラフ について、 に属する頂点のすべての対の道の長さが 以下である場合、 を -クリークという[3]。ふつうのクリークは-クリークである。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.