「離散分離定理」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
 
(2人の利用者による、間の2版が非表示)
1行目: 1行目:
 
'''【りさんぶんりていり (discrete separation theorem)】'''
 
'''【りさんぶんりていり (discrete separation theorem)】'''
  
一般に, あるクラスに属する関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ +\infty \}\,</math> と<math>g: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ -\infty \}\,</math>が <math>f(x) \geq g(x)\,</math> <math>(\forall \ x \in {\mathbf Z}^{n})\,</math>を満たすならば, ある<math>\alpha \in {\mathbf Z}\,</math>, <math>p \in {\mathbf Z}^{n}\,</math>が存在して <math> f(x) \geq \alpha + \langle p, x \rangle  \geq g(x)  \qquad  (\forall \ x \in {\mathbf Z}^{n})\,</math> が成り立つ,という形の定理を離散分離定理という. ここで, <math>\langle p, x \rangle = \sum_{i=1}^{n}p_{i}x_{i}\,</math>であり, <math>p\,</math>が整数ベクトルに選べることが離散性の反映である.
+
一般に, あるクラスに属する関数<math>f: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ +\infty \}\,</math> と<math>g: {\mathbf Z}^{n} \to {\mathbf Z} \cup \{ -\infty \}\,</math>が <math>f(x) \geq g(x)\,</math> <math>(\forall \ x \in {\mathbf Z}^{n})\,</math>を満たすならば, ある<math>\alpha \in {\mathbf Z}\,</math>, <math>p \in {\mathbf Z}^{n}\,</math>が存在して <math> f(x) \geq \alpha + \langle p, x \rangle  \geq g(x)  \qquad  (\forall \ x \in {\mathbf Z}^{n})\,</math> が成り立つ,という形の定理を離散分離定理という. ここで, <math>\textstyle \langle p, x \rangle = \sum_{i=1}^{n}p_{i}x_{i}\,</math>であり, <math>p\,</math>が整数ベクトルに選べることが離散性の反映である.
 +
 
 +
[[Category:グラフ・ネットワーク|りさんぶんりていり]]

2008年11月14日 (金) 09:32時点における最新版

【りさんぶんりていり (discrete separation theorem)】

一般に, あるクラスに属する関数 を満たすならば, ある, が存在して が成り立つ,という形の定理を離散分離定理という. ここで, であり, が整数ベクトルに選べることが離散性の反映である.