クリーク (グラフ理論)
提供: miniwiki
ファイル:Complete graph K5.svg
K5 完全グラフ。部分グラフがこのようになっている場合、その部分グラフの頂点群は大きさ5のクリークを形成している。
ファイル:6n-graf.svg
6個の頂点と7本の辺から成るグラフ。このグラフでは大きさ3の唯一のクリークが 1, 2, 5 である。
グラフ理論において、無向グラフ [math]G=(V, E)[/math] のクリーク（英: clique）とは、頂点の部分集合 [math]C \subseteq V[/math] のうち、[math]C[/math] に属するあらゆる2つの頂点を繋ぐ辺が存在する場合をいう。これはすなわち、[math]C[/math] から誘導される部分グラフが完全だということと等価である。なお、頂点の集合ではなく、そのような部分グラフをクリークと呼ぶこともある。クリークに属する頂点数をそのクリークの大きさと言う。
与えられたグラフに指定された大きさのクリークがあるかどうかを求める問題（クリーク問題、その特殊版が最大クリーク問題）はNP完全である。
クリークの逆の概念を独立集合と呼び、クリークは必ず補グラフの独立集合と対応する。
この用語は、頂点を人、辺を「知っている」という意味としたとき、全ての人が互いに知っていることになるため "clique"（徒党、派閥）と名付けられた。
グラフ [math]G[/math] の最大クリークは理論上重要であり、[math]\omega(G)[/math] で表される。[1]
脚注・出典
- ↑ Godsil, Chris; Gordon Royle [1949] (2004). Algebraic graph theory. New York: Springer. ISBN 0-387-95220-9. , p.3