離散最適化基礎論 (9) 演習問題 2015 年 12 月 25 日岡本吉央提出締切： 2016 年 1 月 8 日講義終了時復習問題 9.1 2 つのマトロイドの交わりがマトロイドであで定義する．このとき，F (S) が E 上のマトロイドでるとは限らないことを証明せよ．あることを証明せよ．(注意：この F (S) という記法は復習問題 9.2 非空な有限集合 E, E 0 と E 0 上のマトロイド広く使われる一般的なものではない．) 2. E 上の任意の独立集合族が有限個のマトロイドの交わりであることを証明せよ．すなわち，E 上の任意の 0 I 0 ⊆ 2E を考える．任意の写像 f : E 0 → E に対して，集合族I を独立集合族 F に対して，ある自然数 k とマトロイド I = {f (X 0 ) | X 0 ∈ I 0 } I1 , . . . , Ik が存在して，で定義する．このとき，I が E 上のマトロイドとなること F = I1 ∩ · · · ∩ Ik を以下の手順に沿って証明せよ． 1. ∅ ∈ I が成り立つことを証明せよ． 2. X ∈ I と Y ⊆ X が成り立つとき，Y ∈ I が成り立つことを証明せよ．(ヒント：演習問題 9.4 の結果を用となることを証明せよ．いてもよい．) 3. X, Y ∈ I が |X| > |Y | を満たすとき，ある要素 e ∈ X − Y が存在して，Y ∪ {e} ∈ I となることを証明せよ．(ヒント：演習問題 9.5 の結果を用いてもよい．) 復習問題 9.3 非空な有限集合 E 上の 2 つのマトロイド I1 , I2 に対して，その合併 I1 ∨ I2 がマトロイドであることを証明せよ．(ヒント：マトロイドの直和がマトロイドであることに着目し，演習問題 9.2 の結果を用いよ．演習問題 9.6 の結果を用いてもよい．) 補足問題 9.4 演習問題 9.2 の設定を考える．集合 X 0 ⊆ E 0 と Y ⊆ E に対して， Y 0 = {x0 | x0 ∈ X 0 , f (x0 ) ∈ Y } と定義するとき，Y = f (Y 0 ) が成り立つことを証明せよ．補足問題 9.5 演習問題 9.2 の設定を考える．集合 X ⊆ E に対して，集合族 FX = {Z 0 | Z 0 ∈ I 0 , X = f (Z 0 )} を考える．FX の中で要素数最小のものを X 0 とする．このとき， |X| = |X 0 | が成り立つことを証明せよ．補足問題 9.6 任意の集合 A, B と任意の写像 f : A → B を考える．任意の部分集合 X, Y ⊆ A に対して， f (X ∪ Y ) = f (X) ∪ f (Y ) が成り立つことを証明せよ．追加問題 9.7 非空な有限集合 E に対して，以下の問いに答えよ． 1. 任意の部分集合 S ⊆ E に対して，集合族 F (S) を F (S) = {X | X ⊆ E, S 6⊆ X} 1