「《凸多面体》」の版間の差分

2007年8月7日 (火) 02:11時点における最新版

【とつためんたい (convex polyhedron) 】

　 $n\,$ 次元実ベクトル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a=(a_1,\cdots,a_n)^{\rm T} \in {\mathbf R}^n\, } と実数 $a_{0}{\in }{\mathbf {R} }\,$ により定まる1次不等式 (線形不等式) $(a_{1}x_{1}+\cdots +a_{n}x_{n}\leq a_{0})\,$ を満たす点 $x=(x_{1},\cdots ,x_{n})^{\rm {T}}\,$ 全体からなる集合を閉半空間(closed halfspace)とよぶ. 有限個の閉半空間の共通部分を凸多面体 (convex polyhedron) とよぶ. すなわち, ${\mathbf {R} }^{n}\,$ 内の凸多面体は, 適当な $m{\times }n\,$ 実行列構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle A\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle m\, } 次元ベクトル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle b\, } を用いて

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P = \{ x \in {\mathbf R}^n \mid Ax \leq b \}\, } 　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (1)\, }

と表現できる. 凸多面体 $P\,$ が, ある正の実数 $M\,$ に対して

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x \in P \;\Longrightarrow\; |x_i| \leq M \quad(i=1,\cdots,n)\, }

をみたすとき有界である(bounded)とよばれ, 英語では convex polytopeと区別してよばれることが多い. 凸多面体の例としては, 線形計画問題での実行可能多面体, TSP多面体, マトロイドの基多面体, ポリマトロイドなどがある.

　凸多面体には不等式表現以外にもう一つ有益な表現方法がある. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell \in {\mathbf R}^n\, } に対して, 適当な構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_1,\cdots,\alpha_\ell \in {\mathbf R}\, } によって

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v = \alpha_1v^1 + \cdots + \alpha_\ell v^\ell\, }

と表現されるベクトル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v\, } を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell\, } の一次結合(線形結合) (linear combination) とよぶ. 係数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_1,\cdots,\alpha_\ell\, } が非負条件

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_1 \geq 0, \cdots , \alpha_\ell \geq 0\, } 　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (2)\, }

をみたす場合には構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v\, } は非負結合(nonnegative combination), 和が1という条件

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_1 + \cdots + \alpha_\ell = 1\, } 　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (3)\, }

をみたす場合には構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v\, } はアフィン結合 (affine combination), さらに (2) と (3) の両方をみたすとき構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v\, } は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell\, } の凸結合 (convex combination) とよばれる. 有限個の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell \in {\mathbf R}^n\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r^1,\cdots,r^d \in {\mathbf R}^n\, } に対して, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell\, } の凸結合と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r^1,\cdots,r^d\, } の非負結合の和として表される点全体, すなわち

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \left\{ x = \sum_{i=1}^\ell \alpha_iv^i + \sum_{j=1}^d \beta_jd^j \;\; \begin{array}{|l} \sum_{i=1}^\ell \alpha_i = 1 \\ \alpha_i \geq 0 \;(i=1,\cdots,\ell) \\ \beta_j \geq 0 \;(j=1,\cdots,d) \end{array} \right\} \, } 　　　　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (4)\, }

と定義される集合は凸多面体となり, 逆に (1) で定義される凸多面体については (4) をみたす有限個の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell \in {\mathbf R}^n\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle r^1,\cdots,r^d \in {\mathbf R}^n\, } が存在することが知られている. 特に, 有界な凸多面体に対しては有限個の点構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle v^1,\cdots,v^\ell \in {\mathbf R}^n\, } の凸結合全体, すなわち,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P = \left\{ x = \sum_{i=1}^\ell \alpha_iv^i \;\; \right| \left. \sum_{i=1}^\ell \alpha_i = 1,\;\; \alpha_i \geq 0 \;(i=1,\cdots,\ell) \right\}\, } 　　　　 $(5)\,$

と表現でき, (5)で定義される集合は, 点集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V=\{v^1,\cdots,v^\ell\}\, } を含む (集合の包含関係の意味で) 最小な凸集合 (convex set)として定義される構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V\, } の凸包 (convex hull) と一致する. 例えば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {(0,0,0),(1,0,0),(0,1,0),(0,0,1)} \subset {\mathbf R}^3\, } の凸包である有界な凸多面体は

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x_1+x_2+x_3 \leq 1,\quad x_1 \geq 0, \quad x_2 \geq 0, \quad x_3 \geq 0\, }

という４本の不等式で表現できる三角錐である.

　点集合 $V=\{v^{1},\cdots ,v^{\ell }\}\subseteq {\mathbf {R} }^{n}\,$ について, どの要素も他の要素たちのアフィン結合で表現できないとき, すなわち,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha_1v^1 + \cdots + \alpha_\ell v^\ell = 0 \;\Longrightarrow\; \alpha_1 = \cdots = \alpha_\ell = 0\, }

をみたすとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V\, } はアフィン独立(affinely independent)であるという. 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle {\mathbf R}^n\, } からは高々構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n{+}1\, } 個のアフィン独立な点しか取れない. 集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S \subseteq {\mathbf R}^n\, } に含まれるアフィン独立な点集合で要素数最大のものを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V=\{v^1,\cdots,v^\ell\}\, } としたとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle S\, } の次元は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \ell{-}1\, } と定義する(次元は $V\,$ の選び方に依存しないことを付記しておく). 先の例では, ${(0,0,0),(1,0,0),(0,1,0),(0,0,1)}\,$ はアフィン独立であり, この凸包である三角錐の次元は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 3\, } となる. 凸多面体構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P \subseteq {\mathbf R}^n\, } の次元が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n\, } であるとき全次元的(full dimensional)という.

　凸多面体構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P \subseteq {\mathbf R}^n\, } に対して, 超平面(hyperplane) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H\, } , すなわち, 非ゼロベクトル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (a_1,\cdots,a_n)^{\rm T} \in {\mathbf R}^n\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a_0 \in {\mathbf R}\, } を用いて

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H = \{x \mid a_1x_1 + \cdots + a_nx_n = a_0 \}\, }

と表現できる集合が

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P \cap H \neq \emptyset \, } 　かつ　構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle P \subseteq \{x \mid a_1x_1 + \cdots + a_nx_n \leq a_0 \}\, }

をみたすとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle H\, } は $P\,$ の支持超平面 (supporting hyperplane) とよばれる. 支持超平面と凸多面体の共通部分も凸多面体である. この共通部分を凸多面体の面 (face) とよび, その次元が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } であるとき構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } 次元面(構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } -face, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } dimensional face)とよぶ. 特に多面体より次元が構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1\, } 小さい面をファセット(facet), 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1\, } 次元面を辺 (edge), 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0\, } 次元面を頂点 (vertex) とよぶ. 先の三角錐を例にすると, 不等式表現の４本に対応する面は $2\,$ 次元面 (ファセット) であり, 他に6個の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1\, } 次元面 (辺) と4個の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 0\, } 次元面 (頂点) を持つ. 一般に有界な凸多面体は頂点全体の凸包と一致し, 全次元的な凸多面体はファセットに対応した不等式で一意的に表現できる (不等式の両辺を正数倍しても同じものとみなす). 凸多面体自身と空集合を便宜上面とすると, 面全体は包含関係に関して束となり, 凸多面体の面束 (face lattice) とよばれる. 同型な面束を持つ凸多面体を互いに組合せ的に同型 (combinatorially equivalent) とよぶ. 束の順序関係を逆にしても束となるが, 任意の凸多面体の面束の順序関係を逆にした束と同型な面束を持つ凸多面体が常に存在し, これは, 元の凸多面体の双対多面体 (dual polytope) とよばれる.

　凸多面体は計算幾何学の重要な研究対象であるばかりでなく, 組合せ最適化問題の実行可能解全体を表現あるいは近似的に表現するための有益な道具である. 多面体理論の項目も参照されたい.

参考文献

[1] A. Brondsted, An Introduction to Convex Polytopes, Springer-Verlag, 1980.

[2] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization, Wiley-Interscience, 1988.

[3] G. M. Ziegler, Lectures on Polytopes, Springer, 1995.

@@ 1行目: / 1行目: @@
 '''【とつためんたい (convex polyhedron) 】'''
-　$n$次元実ベクトル$a=(a_1,\cdots,a_n)^{\rm T} \in {\bf R}^n$と実数 $a_0{\in}{\bf R}$ により定まる1次不等式 (線形不等式) \(    a_1 x_1 + \cdots + a_n x_n \leq a_0\)を満たす点$x = (x_1,\cdots,x_n)^{\rm T}$全体からなる集合を閉半空間(closed halfspace)とよぶ. 有限個の閉半空間の共通部分を[[凸多面体]] (convex polyhedron) とよぶ. すなわち, ${\bf R}^n$内の凸多面体は, 適当な$m{\times}n$実行列$A$と$m$次元ベクトル$b$を用いて
+　<math>n\, </math>次元実ベクトル<math>a=(a_1,\cdots,a_n)^{\rm T} \in {\mathbf R}^n\, </math>と実数 <math>a_0{\in}{\mathbf R}\, </math> により定まる1次不等式 (線形不等式) <math>(a_1 x_1 + \cdots + a_n x_n \leq a_0)\, </math>を満たす点<math>x = (x_1,\cdots,x_n)^{\rm T}\, </math>全体からなる集合を閉半空間(closed halfspace)とよぶ. 有限個の閉半空間の共通部分を[[凸多面体]] (convex polyhedron) とよぶ. すなわち, <math>{\mathbf R}^n\, </math>内の凸多面体は, 適当な<math>m{\times}n\, </math>実行列<math>A\, </math>と<math>m\, </math>次元ベクトル<math>b\, </math>を用いて
-\begin{equation}\label{C-F-01+inequdif}
-    P = \{ x \in {\bf R}^n \mid Ax \leq b \}
-\end{equation}
-と表現できる. 凸多面体$P$が, ある正の実数$M$に対して
+<center>
+<math>P = \{ x \in {\mathbf R}^n \mid Ax \leq b \}\, </math>　　　　<math>(1)\, </math>
+</center>
-    x \in P \;\Longrightarrow\; |x_i| \leq M \quad(i=1,\cdots,n)
-をみたすとき有界である(bounded)とよばれ, 英語では convex polytopeと区別してよばれることが多い. 凸多面体の例としては, [[線形計画]]問題での[[実行可能多面体]], [[TSP多面体]], [[基多面体]], [[ポリマトロイド]]などがある.
+と表現できる. 凸多面体<math>P\, </math>が, ある正の実数<math>M\, </math>に対して
-　凸多面体には不等式表現以外にもう一つ有益な表現方法がある. $v^1,\cdots,v^\ell \in {\bf R}^n$に対して, 適当な$\alpha_1,\cdots,\alpha_\ell \in {\bf R}$によって
-   v = \alpha_1v^1 + \cdots + \alpha_\ell v^\ell
+<center>
+<math>x \in P \;\Longrightarrow\; |x_i| \leq M \quad(i=1,\cdots,n)\, </math>
+</center>
-と表現されるベクトル $v$ を$v^1,\cdots,v^\ell$の一次結合(線形結合)\ (linear combination)とよぶ. 係数$\alpha_1,\cdots,\alpha_\ell$が非負条件
-\begin{equation}\label{C-F-01+shiki1}
+をみたすとき有界である(bounded)とよばれ, 英語では convex polytopeと区別してよばれることが多い. 凸多面体の例としては, [[線形計画]]問題での[[実行可能多面体]], [[TSP多面体]], [[マトロイドの基多面体]], [[ポリマトロイド]]などがある.
-   \alpha_1 \geq 0, \cdots , \alpha_\ell \geq 0
-\end{equation}
-をみたす場合には $v$ は非負結合(nonnegative combination), 和が1という条件
+　凸多面体には不等式表現以外にもう一つ有益な表現方法がある. <math>v^1,\cdots,v^\ell \in {\mathbf R}^n\, </math>に対して, 適当な<math>\alpha_1,\cdots,\alpha_\ell \in {\mathbf R}\, </math>によって
-\begin{equation}\label{C-F-01+shiki2}
-   \alpha_1 + \cdots + \alpha_\ell = 1
-\end{equation}
-をみたす場合には $v$ はアフィン結合 (affine combination), さらに (2) と (3) の両方をみたすとき $v$ は$v^1,\cdots,v^\ell$の凸結合 (convex combination) とよばれる. 有限個の$v^1,\cdots,v^\ell \in {\bf R}^n$と$r^1,\cdots,r^d \in {\bf R}^n$に対して, $v^1,\cdots,v^\ell$の凸結合と$r^1,\cdots,r^d$の非負結合の和として表される点全体, すなわち
+<center>
+<math>v = \alpha_1v^1 + \cdots + \alpha_\ell v^\ell\, </math>
+</center>
-\begin{equation}\label{C-F-01+convdif}
+と表現されるベクトル <math>v\, </math> を<math>v^1,\cdots,v^\ell\, </math>の一次結合(線形結合)  (linear combination) とよぶ. 係数<math>\alpha_1,\cdots,\alpha_\ell\, </math>が非負条件
- \left\{ x = \sum_{i=1}^\ell \alpha_iv^i + \sum_{j=1}^d \beta_jd^j
+<center>
+<math>\alpha_1 \geq 0, \cdots , \alpha_\ell \geq 0\, </math>　　　　<math>(2)\, </math>
+</center>
+をみたす場合には <math>v\, </math> は非負結合(nonnegative combination), 和が1という条件
+<center>
+<math>\alpha_1 + \cdots + \alpha_\ell = 1\, </math>　　　　<math>(3)\, </math>
+</center>
+をみたす場合には <math>v\, </math> はアフィン結合 (affine combination), さらに (2) と (3) の両方をみたすとき <math>v\, </math> は<math>v^1,\cdots,v^\ell\, </math>の凸結合 (convex combination) とよばれる. 有限個の<math>v^1,\cdots,v^\ell \in {\mathbf R}^n\, </math>と<math>r^1,\cdots,r^d \in {\mathbf R}^n\, </math>に対して, <math>v^1,\cdots,v^\ell\, </math>の凸結合と<math>r^1,\cdots,r^d\, </math>の非負結合の和として表される点全体, すなわち
+<center>
+<math> \left\{ x = \sum_{i=1}^\ell \alpha_iv^i + \sum_{j=1}^d \beta_jd^j
       \;\; \begin{array}{|l}
        \sum_{i=1}^\ell \alpha_i = 1 \\
@@ 39行目: / 52行目: @@
        \beta_j \geq 0 \;(j=1,\cdots,d)
       \end{array} \right\}
-\end{equation}
+\, </math>　　　　<math>(4)\, </math>
+</center>
-と定義される集合は凸多面体となり, 逆に (1) で定義される凸多面体については (4) をみたす有限個の$v^1,\cdots,v^\ell \in {\bf R}^n$と$r^1,\cdots,r^d \in {\bf R}^n$が存在することが知られている. 特に, 有界な凸多面体に対しては有限個の点$v^1,\cdots,v^\ell \in {\bf R}^n$の凸結合全体, すなわち,
+と定義される集合は凸多面体となり, 逆に (1) で定義される凸多面体については (4) をみたす有限個の<math>v^1,\cdots,v^\ell \in {\mathbf R}^n\, </math>と<math>r^1,\cdots,r^d \in {\mathbf R}^n\, </math>が存在することが知られている. 特に, 有界な凸多面体に対しては有限個の点<math>v^1,\cdots,v^\ell \in {\mathbf R}^n\, </math>の凸結合全体, すなわち,
-\begin{equation}\label{C-F-01+polydif}
+<center>
- P = \left\{ x = \sum_{i=1}^\ell \alpha_iv^i
+<math>P = \left\{ x = \sum_{i=1}^\ell \alpha_iv^i
       \;\; \right| \left.
        \sum_{i=1}^\ell \alpha_i = 1,\;\; \alpha_i \geq 0 \;(i=1,\cdots,\ell)
-      \right\}
+      \right\}\, </math>　　　　<math>(5)\, </math>
-\end{equation}
+</center>
-と表現でき, (5)で定義される集合は, 点集合$V=\{v^1,\cdots,v^\ell\}$を含む(集合の包含関係の意味で)最小な[[凸集合]] (convex set)として定義される$V$の[[凸包]] (convex hull) と一致する. 例えば, {(0,0,0),(1,0,0),(0,1,0),(0,0,1)} \subset {\bf R}^3$の凸包である有界な凸多面体は
+と表現でき, (5)で定義される集合は, 点集合<math>V=\{v^1,\cdots,v^\ell\}\, </math>を含む (集合の包含関係の意味で) 最小な[[凸集合]] (convex set)として定義される<math>V\, </math>の[[凸包]] (convex hull) と一致する. 例えば, <math>{(0,0,0),(1,0,0),(0,1,0),(0,0,1)} \subset {\mathbf R}^3\, </math>の凸包である有界な凸多面体は
-   x_1+x_2+x_3 \leq 1,\quad
+<center>
+<math>x_1+x_2+x_3 \leq 1,\quad
     x_1 \geq 0, \quad
     x_2 \geq 0, \quad
-    x_3 \geq 0
+    x_3 \geq 0\, </math>
+</center>
 という４本の不等式で表現できる三角錐である.
-　点集合$V=\{v^1,\cdots,v^\ell\} \subseteq {\bf R}^n$について, どの要素も他の要素たちのアフィン結合で表現できないとき, すなわち,
+　点集合<math>V=\{v^1,\cdots,v^\ell\} \subseteq {\mathbf R}^n\, </math>について, どの要素も他の要素たちのアフィン結合で表現できないとき, すなわち,
+<center>
+<math>\alpha_1v^1 + \cdots + \alpha_\ell v^\ell = 0 \;\Longrightarrow\;
+\alpha_1 = \cdots = \alpha_\ell = 0\, </math>
+</center>
- \alpha_1v^1 + \cdots + \alpha_\ell v^\ell = 0 \;\Longrightarrow\;
- \alpha_1 = \cdots = \alpha_\ell = 0
+をみたすとき, <math>V\, </math> はアフィン独立(affinely independent)であるという. <math>{\mathbf R}^n\, </math>からは高々 <math>n{+}1\, </math>個のアフィン独立な点しか取れない. 集合<math>S \subseteq {\mathbf R}^n\, </math>に含まれるアフィン独立な点集合で要素数最大のものを<math>V=\{v^1,\cdots,v^\ell\}\, </math>としたとき, <math>S\, </math>の次元は<math>\ell{-}1\, </math>と定義する(次元は<math>V\, </math>の選び方に依存しないことを付記しておく). 先の例では,<math> {(0,0,0),(1,0,0),(0,1,0),(0,0,1)}\, </math>はアフィン独立であり, この凸包である三角錐の次元は<math>3\, </math>となる. 凸多面体<math>P \subseteq {\mathbf R}^n\, </math>の次元が <math>n\, </math> であるとき全次元的(full dimensional)という.
-をみたすとき, $V$ はアフィン独立(affinely independent)であるという. ${\bf R}^n$からは高々 $n{+}1$個のアフィン独立な点しか取れない. 集合$S \subseteq {\bf R}^n$に含まれるアフィン独立な点集合で要素数最大のものを$V=\{v^1,\cdots,v^\ell\}$としたとき, $S$の次元は$\ell{-}1$と定義する(次元は$V$の選び方に依存しないことを付記しておく). 先の例では, {(0,0,0),(1,0,0),(0,1,0),(0,0,1)}$はアフィン独立であり, この凸包である三角錐の次元は$3$となる. 凸多面体$P \subseteq {\bf R}^n$の次元が $n$ であるとき全次元的(full dimensional)という.
+　凸多面体<math>P \subseteq {\mathbf R}^n\, </math>に対して, 超平面(hyperplane) <math>H\, </math>, すなわち, 非ゼロベクトル<math>(a_1,\cdots,a_n)^{\rm T} \in {\mathbf R}^n\, </math>と<math>a_0 \in {\mathbf R}\, </math>を用いて
-　凸多面体$P \subseteq {\bf R}^n$に対して, 超平面(hyperplane) $H$, すなわち,
-非ゼロベクトル$(a_1,\cdots,a_n)^{\rm T} \in {\bf R}^n$と$a_0 \in {\bf R}$
+<center>
-を用いて
+<math>H = \{x \mid a_1x_1 + \cdots + a_nx_n = a_0 \}\, </math>
+</center>
- H = \{x \mid a_1x_1 + \cdots + a_nx_n = a_0 \}
 と表現できる集合が
- P \cap H \neq \emptyset \quad\mbox{かつ}\quad
+<center>
- P \subseteq \{x \mid a_1x_1 + \cdots + a_nx_n \leq a_0 \}
+<math>P \cap H \neq \emptyset \, </math>　かつ　<math>P \subseteq \{x \mid a_1x_1 + \cdots + a_nx_n \leq a_0 \}\, </math>
+</center>
-をみたすとき, $H$は$P$の支持超平面 (supporting hyperplane) とよばれる. 支持超平面と凸多面体の共通部分も凸多面体である. この共通部分を凸多面体の面 (face) とよび, その次元が$k$であるとき$k$次元面($k$-face, $k$ dimensional face)とよぶ. 特に多面体より次元が$1$小さい面をファセット(facet), $1$次元面を辺 (edge), $0$次元面を頂点 (vertex) とよぶ. 先の三角錐を例にすると, 不等式表現の４本に対応する面は$2$次元面 (ファセット) であり, 他に6個の$1$次元面 (辺) と4個の$0$次元面 (頂点) を持つ. 一般に有界な凸多面体は頂点全体の凸包と一致し, 全次元的な凸多面体はファセットに対応した不等式で一意的に表現できる (不等式の両辺を正数倍しても同じものとみなす). 凸多面体自身と空集合を便宜上面とすると, 面全体は包含関係に関して束となり, 凸多面体の面束 (face lattice) とよばれる. 同型な面束を持つ凸多面体を互いに組合せ的に同型 (combinatorially equivalent) とよぶ. 束の順序関係を逆にしても束となるが, 任意の凸多面体の面束の順序関係を逆にした束と同型な面束を持つ凸多面体が常に存在し, これは, 元の凸多面体の双対多面体 (dual polytope) とよばれる.
+をみたすとき, <math>H\, </math>は<math>P\, </math>の支持超平面 (supporting hyperplane) とよばれる. 支持超平面と凸多面体の共通部分も凸多面体である. この共通部分を凸多面体の面 (face) とよび, その次元が<math>k\, </math>であるとき<math>k\, </math>次元面(<math>k\, </math>-face, <math>k\, </math> dimensional face)とよぶ. 特に多面体より次元が<math>1\, </math>小さい面をファセット(facet), <math>1\, </math>次元面を辺 (edge), <math>0\, </math>次元面を頂点 (vertex) とよぶ. 先の三角錐を例にすると, 不等式表現の４本に対応する面は<math>2\, </math>次元面 (ファセット) であり, 他に6個の<math>1\, </math>次元面 (辺) と4個の<math>0\, </math>次元面 (頂点) を持つ. 一般に有界な凸多面体は頂点全体の凸包と一致し, 全次元的な凸多面体はファセットに対応した不等式で一意的に表現できる (不等式の両辺を正数倍しても同じものとみなす). 凸多面体自身と空集合を便宜上面とすると, 面全体は包含関係に関して束となり, 凸多面体の面束 (face lattice) とよばれる. 同型な面束を持つ凸多面体を互いに組合せ的に同型 (combinatorially equivalent) とよぶ. 束の順序関係を逆にしても束となるが, 任意の凸多面体の面束の順序関係を逆にした束と同型な面束を持つ凸多面体が常に存在し, これは, 元の凸多面体の双対多面体 (dual polytope) とよばれる.
 　凸多面体は[[計算幾何学]]の重要な研究対象であるばかりでなく, [[組合せ最適化問題]]の実行可能解全体を表現あるいは近似的に表現するための有益な道具である. [[多面体理論]]の項目も参照されたい.
@@ 94行目: / 114行目: @@
 ----
 '''参考文献'''
@@ 102行目: / 121行目: @@
 [3] G. M. Ziegler, ''Lectures on Polytopes'', Springer, 1995.
+[[Category:計算幾何|とつためんたい]]

「《凸多面体》」の版間の差分

2007年8月7日 (火) 02:11時点における最新版

案内メニュー

検索