クリーク (グラフ理論)

グラフ理論において、無向グラフ  のクリーク（）とは、頂点の部分集合  のうち、 に属するあらゆる2つの頂点を繋ぐ辺が存在するものをいう。これはすなわち、 から誘導される部分グラフが完全だということである。なお、頂点の集合ではなく、そのような部分グラフをクリークと呼ぶこともある。（また包含関係に関して極大な完全部分グラフのみをクリークと呼ぶこともあるので注意がいる。）クリークに属する頂点数をそのクリークの大きさと言う。

与えられたグラフに指定された大きさのクリークがあるかどうかを求める問題（クリーク問題、その特殊版が最大クリーク問題）はNP完全である。

クリークの逆の概念を独立集合と呼び、クリークは必ず補グラフの独立集合と対応する。

この用語は、頂点を人、辺を「知っている」という意味としたとき、全ての人が互いに知っていることになるため ""（徒党、派閥）と名付けられた。

グラフ  の最大クリークは理論上重要であり、 で表される。

脚注・出典

関連項目 
 グラフ理論
 最小クリーク被覆問題

外部リンク 
 Cliquer, 任意の重み付きグラフでクリークを求めるためのC言語ルーチン群

グラフ理論オブジェクト
数学に関する記事