凸多面体と単体的複体 （理論とソフトウェア）

Presentation on theme: "凸多面体と単体的複体 （理論とソフトウェア）"— Presentation transcript:

1 凸多面体と単体的複体 （理論とソフトウェア）
2003年度 演習Ⅲ 2.3 計算幾何的アプローチ April 9, 2003 博士課程2年 森山園子 2003年度演習Ⅲの 2.3 計算幾何的アプローチを担当させて頂きます博士課程2年森山園子です。 今日は不在で 演習内容は「凸多面体と単体的複体」です。 まずは，凸多面体と単体的複体について，簡単に説明させて頂きます。

2 線形計画問題と凸多面体 線形計画法の許容領域 許容領域は凸多面体 線形計画問題とは？ …多面体上で1次関数の最小化
max x1 + 2x2 + 3x3 s.t. x1 + 2x3 ≦3 x2 + 2x3 ≦2 x1, x2, x3 ≧0 x3 線形計画法の許容領域 (有限本の1次等式あるいは 等号付1次不等式） 許容領域は凸多面体 1 2 x2 O (1,0,1) 線形計画問題とは？ …多面体上で1次関数の最小化 （または最大化）を行う問題 凸多面体については，3年夏学期の離散数学の授業で線形計画法を勉強した折に登場したと思います。 有限本の1次等式あるいは等号付1次不等式で与えられる線形計画法の許容領域が凸多面体であることを利用して，線形計画問題を幾何的アプローチから考察するというものでした。 ここでは単なるモデルとして多面体を扱いましたが，ここから発展して「多面体の正確な定義とは何か？」「多面体はどんな性質を持つのか？」「どういった種類の多面体が存在するのか」と言った問題が考えられると思います。 3 (3,2,0) x1

3 凸多面体とは？ オイラーの公式 [頂点数] – [枝数] + [三角形数] (= 6 – 12 + 8) = 2 オイラー・ポワンカレの公式
皆さんが中高で勉強した「多面体」とは正確には「3次元凸多面体」のことです。 3次元凸多面体は有名な「オイラーの公式」([頂点数]-[枝数]+[三角形数]=2)を満たします。 この図の多面体は頂点数6，枝数12，三角形数8から構成されており，オイラーの公式を満たすことがわかります。 御想像がつくと思いますが，多面体の定義は一般d次元で与えられています。 このd次元凸多面体に対応するオイラーの公式は＜アニメーション＞この「オイラー・ポワンカレの公式」です。 これはオイラーの公式の一般化であり，d=3 の場合がオイラーの公式になっています。 今回の演習では，3次元凸多面体の世界から離れて一般d次元凸多面体の定義・性質を扱います。 オイラー・ポワンカレの公式 -1 + f0 – f1 + f2 … + (-1)d-1fd-1 + (-1)d = 0  d=3：オイラーの公式

4 グラフとは？ 1 4 1 4 2 3 2 3 頂点どうしの関係を枝で記述 枝どうしの関係を頂点で記述 （1次元単体的複体）
次は，単体的複体についてです。 凸多面体には多少馴染があったと思いますが，単体的複体は殆んどの方が始めて耳にする単語かもしれません。 離散数学で勉強した「グラフ」との関連から単体的複体を定義します。 グラフは，「頂点どうしの関係を枝で記述したもの」として認識されますが＜アニメーション＞ ，別の見方として＜アニメーション＞枝どうしの関係を頂点で記述したと考えることもできます＜アニメーション＞ 。 この見方から，グラフを一般化したのが単体的複体です。 グラフは1次元単体的複体に対応します。 2 3 2 3

5 単体的複体とは? 5 2 1 3 4 d次元単体どうしの関係を(d-1)次元以下の単体で記述 例：d次元単体的複体 d=0: 頂点集合
2次元単体的複体Δ ={Φ(空集合), 1, 2, 3, 4, 5, 12, 13, 23, 24, 25, 34, 45, 123, 234, 245} つまり，一般d次元単体的複体は「d次元単体どうしの関係を(d-1)次元以下の単体で記述したもの」に対応します。 d次元単体とは，(d+1)個の頂点からなるアフィン包のことです。 つまり，(-1)次元単体は空集合，0次元単体は頂点，1次元単体は枝，2次元単体は三角形，3次元単体は四面体…となります。 例えば，0次元単体的複体は頂点集合に対応し，1次元単体的複体は「頂点で連結された枝集合，つまりグラフ」であり，2次元単体的複体は「頂点または枝で連結された三角形集合」…となります。 d次元単体的複体は，「面集合」と呼ばれる，(-1)次元単体からd次元単体の全ての単体集合で与えられますが，単体的複体の定義からd次元単体集合のみで十分です。 この図で示した2次元単体的複体の面集合は中カッコ内に囲まれた全ての単体集合ですが，実際には赤で色付けした三角形集合のみの表現で十分です。 1 3 4

6 凸多面体と単体的複体との関係 Shellable 凸多面体 単体的複体 マトロイド複体 純な単体的複体
今まで説明してきた凸多面体と単体的複体には図のような包含関係があり，様々な種類の凸多面体・単体的複体が存在します。 このマトロイド複体とは，マトロイドの独立集合族が多面体・単体的複体の面集合に対応するものです。 また，凸多面体・単体的複体には色々な性質が定義されています。 森山は，特に＜アニメーション＞シェラブルという性質について研究してきました。 純な単体的複体

7 演習内容 凸多面体と単体的複体の理解 関連論文を読む 実装
そこで，今回の演習ではこの Lectures on Polytopes を参考文献として凸多面体・単体的複体の性質を理解して頂き，その後で関連論文を読んで更なる理解を深めて頂こうと考えています。 場合によっては実装とも考えております。 関連論文の選択や実装等については，皆さんと相談して決めるつもりですので，御安心下さい。