離散分離定理のソースを表示

'''【りさんぶんりていり (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>\textstyle \langle p, x \rangle = \sum_{i=1}^{n}p_{i}x_{i}\,</math>であり, <math>p\,</math>が整数ベクトルに選べることが離散性の反映である.

[[Category:グラフ･ネットワーク|りさんぶんりていり]]