離散分離定理

提供: ORWiki
2007年7月9日 (月) 18:16時点における122.17.2.240 (トーク)による版 (新しいページ: ''''【りさんぶんりていり (discrete separation theorem)】''' 一般に, あるクラスに属する関数$f: {\bf Z}\sp{n} \to {\bf Z} \cup \{ +\infty \}$ と$g: {\bf...')
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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

一般に, あるクラスに属する関数$f: {\bf Z}\sp{n} \to {\bf Z} \cup \{ +\infty \}$ と$g: {\bf Z}\sp{n} \to {\bf Z} \cup \{ -\infty \}$が $f(x) \geq g(x)$ $(\forall \ x \in {\bf Z}\sp{n})$を満たすならば, ある$\alpha \in {\bf Z}$, $p \in {\bf Z}\sp{n}$が存在して $ f(x) \geq \alpha + \langle p, x \rangle \geq g(x) \qquad (\forall \ x \in {\bf Z}\sp{n})$ が成り立つ,という形の定理を離散分離定理という. ここで, $\langle p, x \rangle = \sum_{i=1}\sp{n}p_{i}x_{i}$であり, $p$が整数ベクトルに選べることが離散性の反映である.