離散最適化基礎論 (6) 2014 年 11 月 14 日演習問題岡本吉央

離散最適化基礎論 (6)
演習問題
2014 年 11 月 14 日
岡本吉央
提出締切： 2014 年 11 月 28 日
復習問題 6.1 行列 A ∈ Zm×n とベクトル b ∈ Zm を用い
て定義された凸多面体 P = {x ∈ Rn | Ax ≤ b} を考える．
行列 A の任意の n 次正方部分行列の行列式が −1, 0, 1 のい
ずれかであるとき，P が整凸多面体となること，すなわち，
P のすべての頂点の座標が整数となることを証明せよ．ヒ
ント：Cramer の公式を利用するとよい．
復習問題 6.2 任意の整数ベクトル v1 , . . . , vk ∈ Zn が生成
する凸多面錐 C を考える．このとき，C の Hilbert 生成系
が存在することを証明せよ．
発展復習問題 6.3 任意の整数ベクトル v1 , . . . , vk ∈ Zn が
生成する凸多面錐 C を考える．凸多面錐 C が pointed で
あるとき，C の Hilbert 基底が一意に存在することを証明
せよ．
( ) ( ) ( )
2
1
1
復習問題 6.4 3 つのベクトル
,
,
が生成す
1
1
3
る凸多面錐の Hilbert 基底を答えよ．
( ) ( )
7
2
追加問題 6.5 2 つのベクトル
,
が生成する凸多
2
5
面錐の Hilbert 基底を答えよ．
     
1
1
0
     
追加問題 6.6 3 つのベクトル 1 , 0 , 1 が生成す
0
1
る凸多面錐の Hilbert 基底を答えよ．
1
追加問題 6.7 次の命題は正しくない．反例を挙げよ．
命題：ベクトル v1 , . . . , vk が生成する凸多面錐
の Hilbert 生成系は必ず v1 , . . . , vk を要素とし
て含む．
追加問題 6.8 平面における 2 つのベクトル v1 , v2 ∈ Z2 が
生成する凸多面錐の Hilbert 基底が {v1 , v2 } であるとする．
このとき，v1 と v2 を並べてできる 2 × 2 行列 (v1 v2 ) の行
列式が 1 か −1 になることを証明せよ．ヒント：ベクトル
v1 , v2 が生成する平行四辺形の面積が行列 (v1 v2 ) の行列式
の絶対値と等しいという事実を用いてもよい．
1

Download Report