最大クリーク問題

OR事典

最大クリーク問題

読み方：さいだいくりーくもんだい
【英】：maximum clique problem

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

「OR事典」の他の用語

組合せ最適化：

巡回セールスマン問題  整数計画  施設配置問題  最大クリーク問題  最小木問題  最短路問題  最適性の原理

ウィキペディア

最大クリーク問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/02/13 05:21 UTC 版)

最大クリーク問題（さいだいクリークもんだい）は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）の中で最大のものを見つける問題。NP困難であることが知られている。