ロバース数

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

【ろばーすすう (Lov\'asz number)】

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