クリーク (グラフ理論)

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

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

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

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

グラフ ${\displaystyle G}$ の最大クリークは理論上重要であり、${\displaystyle \omega (G)}$ で表される。

${\displaystyle n}$-クリーク

グラフ ${\displaystyle G}$ の部分グラフ ${\displaystyle C}$ について、 ${\displaystyle C}$ に属する頂点のすべての対の道の長さが ${\displaystyle n}$ 以下である場合、 ${\displaystyle C}$ を ${\displaystyle n}$-クリークという。ふつうのクリークは${\textstyle 1}$-クリークである。

脚注・出典

関連項目

• グラフ理論
• 最小クリーク被覆問題

外部リンク

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

1. グラフ理論
2. 理論
3. クリーク
4. 次数 (グラフ理論)
5. 数学
6. 最大クリーク問題
7. 全域木
8. ゲーム理論
9. 補グラフ
10. 径
11. アルゴリズム
12. 辺
13. 完全グラフ
14. 直線
15. 幾何学
16. パーフェクトグラフ
17. モデル理論
18. 秋山仁
19. 誘導部分グラフ
20. グラフ彩色