「ロバース数」の版間の差分
ナビゲーションに移動
検索に移動
Albeit-Kun (トーク | 投稿記録) |
|||
| (2人の利用者による、間の2版が非表示) | |||
| 1行目: | 1行目: | ||
| − | '''【ろばーすすう (Lov | + | '''【ろばーすすう (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困難であるのに対し, は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.
