最大クリーク問題

提供: ORWiki
2007年7月12日 (木) 15:18時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【さいだいくりーくもんだい (maximum clique problem)】''' 与えられた無向グラフ $G=(V,E)$ に対して, 頂点の集合 $K (\subseteq V)$ の任意の...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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

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

「https://orsj-ml.org/orwiki/wiki/index.php?title=最大クリーク問題&oldid=3039」から取得