「ロバース数」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
'''【ろばーすすう (Lov\'asz number)】'''
+
'''【ろばーすすう (Lovász number)】'''
  
 
与えられた無向グラフ<math>G\,</math>に対して定義される数値 (<math>\vartheta (G)\,</math>と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. <math>G\,</math>のクリーク数<math>w(G)\,</math>と彩色数<math>\chi (G)\,</math>に対し, <math>w(G) \leq \vartheta (\overline{G}) \leq  \chi (G)\,</math> が成り立つ事が知られている, ただし <math>\overline{G}\,</math> は<math>G\,</math>の補グラフである.<math>w(G), \chi (G)\,</math> を求めるのはNP困難であるのに対し, <math>\vartheta (\overline{G})\,</math>は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.
 
与えられた無向グラフ<math>G\,</math>に対して定義される数値 (<math>\vartheta (G)\,</math>と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. <math>G\,</math>のクリーク数<math>w(G)\,</math>と彩色数<math>\chi (G)\,</math>に対し, <math>w(G) \leq \vartheta (\overline{G}) \leq  \chi (G)\,</math> が成り立つ事が知られている, ただし <math>\overline{G}\,</math> は<math>G\,</math>の補グラフである.<math>w(G), \chi (G)\,</math> を求めるのはNP困難であるのに対し, <math>\vartheta (\overline{G})\,</math>は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.
 +
 +
[[Category:組合せ最適化|ろばーすすう]]

2008年11月14日 (金) 09:52時点における最新版

【ろばーすすう (Lovász number)】

与えられた無向グラフに対して定義される数値 (と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. のクリーク数と彩色数に対し, が成り立つ事が知られている, ただし の補グラフである. を求めるのはNP困難であるのに対し, は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.