「ロバース数」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【ろばーすすう (Lov\'asz number)】''' 与えられた無向グラフ$G$に対して定義される数値 ($\vartheta (G)$と書かれる事が多い)で, グラフ...') |
|||
| 1行目: | 1行目: | ||
'''【ろばーすすう (Lov\'asz number)】''' | '''【ろばーすすう (Lov\'asz 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>は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる. |
2007年7月11日 (水) 17:23時点における版
【ろばーすすう (Lov\'asz number)】
与えられた無向グラフに対して定義される数値 (と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. のクリーク数と彩色数に対し, が成り立つ事が知られている, ただし はの補グラフである. を求めるのはNP困難であるのに対し, は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.
