離散最適化基礎論 (7) 2015 年 12 月 4 日演習問題岡本吉央

離散最適化基礎論 (7)
演習問題
2015 年 12 月 4 日
岡本吉央
提出締切： 2015 年 12 月 18 日講義終了時
5. 上の小問における e0 が e0 ∈ C(e, B 0 ) を満たすことを
証明せよ．
復習問題 7.1 非空な有限集合 E 上のマトロイド I ⊆ 2E
に対して，C は I のサーキットであり，C ⊆ X ⊆ E とす
6. 演習問題 7.5 を用いて，(B−{e})∪{e0 } と (B 0 −{e0 })∪
{e} が I の基であることを証明せよ．
る．このとき，X 6∈ I であることを証明せよ．
復習問題 7.2 非空な有限集合 E 上のマトロイド I ⊆ 2E に
対して，C, C 0 は I のサーキットであるとする．このとき，
C ⊆ C 0 ならば C = C 0 であることを証明せよ．
に対して，C, C 0 を I の異なるサーキット，e ∈ C ∩ C 0 ，
復習問題 7.3 非空な有限集合 E 上のマトロイド I ⊆ 2 に
f ∈ C − C 0 とする．以下の問いに答えよ．
1. r : 2E → R をマトロイド I の階数関数であるとする．
E
対して，C, C 0 は I の異なるサーキットであり，e ∈ C ∩ C 0
であるとする．このとき，I のあるサーキット C 00 に対し
00
補足問題 7.7 非空な有限集合 E 上のマトロイド I ⊆ 2E
このとき，r((C ∪ C 0 ) − {e, f }) = r(C ∪ C 0 ) が成り
0
て，C ⊆ (C ∪ C ) − {e} が成り立つことを，以下の手順に
立つことを証明せよ．
2. 集合 B ⊆ E を (C ∪ C 0 ) − {e, f } の基であるとする．
このとき，B ∪ {f } が I のサーキットを含むことを証
明せよ．
従って証明せよ．
1. C ∩ C 0 ∈ I が成り立つことを証明せよ．
2. マトロイド I の階数関数 r : 2E → R+ に対して，r(C∪
C 0 ) ≤ |C ∪ C 0 | − 2 が成り立つことを証明せよ．
3. C ∪ C 0 − {e} がマトロイド I の従属集合であること
3. 条件 f ∈ C 00 ⊆ (C ∪ C 0 ) − {e} を満たすサーキット
C 00 が存在することを証明せよ．
を証明せよ．
追加問題 7.8 非空な有限集合 E 上のマトロイド I ⊆ 2E
復習問題 7.4 非空な有限集合 E 上のマトロイド I ⊆ 2E
を考える．任意の X ∈ I と任意の e ∈ E − X に対して，
X ∪ {e} が従属ならば，X ∪ {e} が I のサーキットをただ
1 つ含むことを証明せよ．
に対して，C を I のサーキットとして，e ∈ C とする．こ
のとき，C = C(e, B) を満たす I の基 B が存在することを
証明せよ．
追加問題 7.9 非空な有限集合 E 上のマトロイド I ⊆ 2E
復習問題 7.5 非空な有限集合 E 上のマトロイド I ⊆ 2E
に対して，B を I の基として，e ∈ E ，e0 ∈ E − B とする．
を考える．マトロイド I の基 B と e, e0 ∈ E に対して，e ∈
このとき，(B − {e}) ∪ {e0 } が I の基であるための必要十
C(e0 , B) ならば (B − {e}) ∪ {e0 } も I の基であることを証
分条件が e ∈ C(e0 , B) を満たすことであることを証明せよ．
明せよ．ただし，C(e0 , B) は B に関する e0 の基本サーキッ
トを表す．(ヒント：演習問題 3.7 を用いてもよい)
発展復習問題 7.6 非空な有限集合 E 上のマトロイド I ⊆ 2E
に対して，その基 B, B 0 と任意の e ∈ B を考える基の同時
交換公理を以下の手順に従って証明せよ．
1. 基本サーキット C(e, B 0 ) を C 0 と置く．次の集合族を
考える．
F = {C ∈ C | e ∈ C ⊆ B ∪ B 0 , C − B ⊆ C 0 − B}.
ただし，C はマトロイド I のサーキット族である．こ
のとき，F 6= ∅ であることを証明せよ．
2. F の要素 C で |C − B| を最小とするものを C ∗ とす
る．このとき，|C ∗ − B| ≥ 1 であることを証明せよ．
3. 上の小問における C ∗ が |C ∗ − B| = 1 を満たすこと
を証明せよ．(ヒント：演習問題 7.7 を用いてよい．)
4. 上の小問より，ある e0 ∈ E が存在して，C ∗ −B = {e0 }
となる．このとき，C ∗ = C(e0 , B) と e ∈ C ∗ が成り
立つことを証明せよ．
1

Download Report