「最大クリーク問題」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(新しいページ: ''''【さいだいくりーくもんだい (maximum clique problem)】''' 与えられた無向グラフ $G=(V,E)$ に対して, 頂点の集合 $K (\subseteq V)$ の任意の...')
 
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
 
'''【さいだいくりーくもんだい (maximum clique problem)】'''
 
'''【さいだいくりーくもんだい (maximum clique problem)】'''
  
−
与えられた無向グラフ $G=(V,E)$ に対して, 頂点の集合 $K (\subseteq V)$ の任意の2頂点が隣接しているとき, すなわち, 辺で結ばれているとき $K$ を $G$のクリーク(clique)と呼ぶ. 要素数最大のクリークを求める問題を最大クリーク問題と呼ぶ. 最大クリークの大きさをクリーク数(clique number)と呼ぶ. さらに, 各頂点に重みが与えられたもとで, 重みの総和最大のクリークを求める問題などバリエーションがある.
+
与えられた無向グラフ <math>G=(V,E) \,</math> に対して, 頂点の集合 <math>K (\subseteq V) \,</math> の任意の2頂点が隣接しているとき, すなわち, 辺で結ばれているとき <math>K \,</math> を <math>G \,</math>のクリーク(clique)と呼ぶ. 要素数最大のクリークを求める問題を最大クリーク問題と呼ぶ. 最大クリークの大きさをクリーク数(clique number)と呼ぶ. さらに, 各頂点に重みが与えられたもとで, 重みの総和最大のクリークを求める問題などバリエーションがある.
 +
 
 +
[[Category:組合せ最適化|さいだいくりーくもんだい]]

2008年11月9日 (日) 17:56時点における最新版

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

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

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