最大クリーク問題

出典: ORWiki

【さいだいくりーくもんだい (maximum clique problem)】

与えられた無向グラフ $G=(V,E) \,$ に対して, 頂点の集合 $K (\subseteq V) \,$ の任意の2頂点が隣接しているとき, すなわち, 辺で結ばれているとき $K \,$ を $G \,$ のクリーク(clique)と呼ぶ. 要素数最大のクリークを求める問題を最大クリーク問題と呼ぶ. 最大クリークの大きさをクリーク数(clique number)と呼ぶ. さらに, 各頂点に重みが与えられたもとで, 重みの総和最大のクリークを求める問題などバリエーションがある.