ロバース数

提供: ORWiki
2007年7月16日 (月) 16:27時点における122.17.2.240 (トーク)による版
ナビゲーションに移動 検索に移動

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

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