ロバース数 - 版の履歴

2008年11月14日 (金) 00:52にAlbeit-Kunによる

2008-11-14T00:52:47Z

Orsjwiki: "ロバース数" を保護しました。 [edit=sysop:move=sysop]

2007-07-20T00:52:48Z

"ロバース数" を保護しました。 [edit=sysop:move=sysop]

2007年7月16日 (月) 07:27に122.17.2.240による

2007-07-16T07:27:56Z

2007年7月11日 (水) 08:23に211.9.146.139による

2007-07-11T08:23:11Z

122.17.2.240: 新しいページ: ''''【ろばーすすう (Lov\'asz number)】''' 与えられた無向グラフ$G$に対して定義される数値 ($\vartheta (G)$と書かれる事が多い)で, グラフ...'

2007-07-09T07:01:10Z

新しいページ: ''''【ろばーすすう (Lov\'asz number)】''' 与えられた無向グラフ$G$に対して定義される数値 ($\vartheta (G)$と書かれる事が多い)で, グラフ...'

新規ページ

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

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

← 古い版		2008年11月14日 (金) 00:52時点における版
2行目:		2行目:

	与えられた無向グラフ<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:組合せ最適化\|ろばーすすう]]

← 古い版		2007年7月16日 (月) 07:27時点における版
1行目:		1行目:
−	'''【ろばーすすう (Lov~~\'asz~~ number)】'''	+	'''【ろばーすすう (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>は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.

← 古い版		2007年7月11日 (水) 08:23時点における版
1行目:		1行目:
	'''【ろばーすすう (Lov\'asz number)】'''		'''【ろばーすすう (Lov\'asz number)】'''

−	与えられた無向グラフ$G$に対して定義される数値 ($\vartheta (G)$と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. $G$のクリーク数$w(G)$と彩色数$\chi (G)$に対し, $w(G) \leq \vartheta (\overline{G}) \leq \chi (G)$ が成り立つ事が知られている, ただし $\overline{G}$ は$G$の補グラフである.$w(G), \chi (G)$ を求めるのはNP困難であるのに対し, $\vartheta (\overline{G})$は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.	+	与えられた無向グラフ<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月20日 (金) 00:52時点における版
(相違点なし)