クリーク (グラフ理論)

6個の頂点と7本の辺から成るグラフ。このグラフでは大きさ3の唯一のクリークが 1, 2, 5 である。

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

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

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

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

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

$n$ -クリーク

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

脚注・出典

^ Gross, J. L.; Yellen, J.; Zhang, P. (2014). Handbook of Graph Theory (2nd ed.). CRC Press. p. xiv. ISBN 978-1-4398-8019-7
^ Godsil, Chris; Gordon Royle (2004) [1949]. Algebraic graph theory. New York: Springer. ISBN 0-387-95220-9 , p.3
^ Doreian, Patrick (1970). Mathematics and the study of social relations. London: Weidenfeld and Nicolson. ISBN 978-0-297-00258-1

外部リンク

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

[1] Gross, J. L.; Yellen, J.; Zhang, P. (2014). Handbook of Graph Theory (2nd ed.). CRC Press. p. xiv. ISBN 978-1-4398-8019-7

[2] Godsil, Chris; Gordon Royle (2004) [1949]. Algebraic graph theory. New York: Springer. ISBN 0-387-95220-9 , p.3

[3] Doreian, Patrick (1970). Mathematics and the study of social relations. London: Weidenfeld and Nicolson. ISBN 978-0-297-00258-1

[1]

[2]

[3]

n {\displaystyle n} -クリーク

脚注・出典

関連項目

外部リンク

$n$ -クリーク