凸多面体と単体的複体
（理論とソフトウェア）
2003年度 演習Ⅲ 2.3 計算幾何的アプローチ
April 9, 2003
博士課程2年 森山園子
[email protected]
線形計画問題と凸多面体
max x1 + 2x2 + 3x3
s.t. x1 + 2x3 ≦3
x2 + 2x3 ≦2
x1, x2, x3 ≧0
x3
線形計画法の許容領域
(有限本の1次等式あるいは 1
等号付1次不等式）
許容領域は凸多面体
2
O
x2
(1,0,1)
線形計画問題とは？
…多面体上で1次関数の最小化
（または最大化）を行う問題
3
x1
(3,2,0)
凸多面体とは？
オイラーの公式
[頂点数] – [枝数] + [三角形数]
(= 6 – 12 + 8)
=2
オイラー・ポワンカレの公式
-1 + f0 – f1 + f2 … + (-1)d-1fd-1 + (-1)d = 0
 d=3：オイラーの公式
グラフとは？
頂点どうしの関係を枝で記述 枝どうしの関係を頂点で記述
（1次元単体的複体）
1
4
1
4
2
3
2
3
単体的複体とは?
 d次元単体どうしの関係を(d-1)次元以下の単体で記述
 例：d次元単体的複体
 d=0: 頂点集合
 d=1: 頂点で連結された枝集合  グラフ
 d=2: 頂点または枝で連結された三角形集合
5
2
1
3
4
2次元単体的複体Δ
={Φ(空集合),
1, 2, 3, 4, 5,
12, 13, 23, 24, 25, 34, 45,
123, 234, 245}
凸多面体と単体的複体との関係
Shellable
凸多面体
単体的複体
マトロイド複体
純な単体的複体
演習内容
 凸多面体と単体的複体の理解
 関連論文を読む
 実装

情報科学演習3 --- 計算代数とその応用