クリーク (グラフ理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
K5 完全グラフ。部分グラフがこのようになっている場合、その部分グラフの頂点群は大きさ5のクリークを形成している。
6個の頂点と7本の辺から成るグラフ。このグラフでは大きさ3の唯一のクリークが 1, 2, 5 である。

グラフ理論において、無向グラフ G = (VE) のクリーク: clique)とは、頂点の部分集合 C ⊆ V のうち、C に属するあらゆる2つの頂点を繋ぐ辺が存在する場合をいう。これはすなわち、C から誘導される部分グラフ完全だということと等価である。なお、頂点の集合ではなく、そのような部分グラフをクリークと呼ぶこともある。クリークに属する頂点数をそのクリークの大きさと言う。

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

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

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

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

脚注・出典[編集]

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

関連項目[編集]

外部リンク[編集]

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