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

提供: ORWiki
ナビゲーションに移動 検索に移動
("ロバース数" を保護しました。 [edit=sysop:move=sysop])
(相違点なし)

2007年7月20日 (金) 09:52時点における版

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

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