離散最適化基礎論 (2) 演習問題 2015 年 10 月 23 日岡本吉央提出締切： 2015 年 10 月 30 日講義終了時復習問題 2.1 次に挙げる，有限集合 E = {1, 2, 3} 上の有追加問題 2.8 非空な有限集合 E 上の分割マトロイドとは，E 限集合族 I はマトロイドではない．なぜマトロイドではなの分割 {E1 , . . . , Ek } と自然数 r1 , . . . , rk ≥ 0 に対して I = いのか説明せよ． {X ⊆ E | すべての i ∈ {1, . . . , k} に対して |X ∩Ei | ≤ ri } として定義される有限集合族 I である． E = {1, 2, 3, 4, 5} のとき，E の分割 {E1 , . . . , Ek } と自然 1. I = {∅, {1}, {3}, {1, 3}, {2, 3}}. 数 r1 , . . . , rk ≥ 0 が次のように与えられたとき，そこから 2. I = {∅, {1}, {2}, {3}, {1, 3}}. 定義される分割マトロイドが何であるか，その要素をすべ復習問題 2.2 非空な有限集合 E と自然数 r ≥ 0 を考える．て並べることで答えよ．このとき，有限集合族 1. k = 2, E1 = {1, 2, 3}, E2 = {4, 5}, r1 = 1, r2 = 2. I = {X ⊆ E | |X| ≤ r} 2. k = 3, E1 = {1}, E2 = {2, 3, 4}, E3 = {5}, r1 = 1, r2 = 1, r3 = 1. が E 上のマトロイドであることを証明せよ． 3. k = 3, E1 = {1, 2}, E2 = {3}, E3 = {4, 5}, r1 = 0, 復習問題 2.3 Rm において線形独立であるベクトルの集合 X, Y を考える．任意の x ∈ X − Y に対して，Y ∪ {x} が線形独立ではないと仮定する．このとき，任意のベクトル r2 = 1, r3 = 2. 追加問題 2.9 非空な有限集合 E と有限集合族 F ⊆ 2E を x ∈ X に対して，hY ∪ {x}i = hY i が成り立つことを証明せよ．考える．このとき，F が E 上のマトロイドであるとき，そのときに限り，F が次の 3 条件をともに満たすことを証明復習問題 2.4 自然数 m, n ≥ 1 に対して，任意のベクトルせよ． a1 , a2 , . . . , an ∈ Rm を考え，集合 E を E = {a1 , a2 , . . . , an } と定義する．このとき，有限集合族 1. ∅ ∈ F ． 2. X ∈ F かつ Y ⊆ X ならば，Y ∈ F ． I = {X ⊆ E | X は線形独立 } 3. X, Y ∈ F かつ |X| = |Y | + 1 ならば，ある e ∈ X − Y が E 上のマトロイドであることを証明せよ．(注：問題 2.5 が存在して，Y ∪ {e} ∈ F ．を用いてもよい．) 補足問題 2.5 Rm において線形独立であるベクトルの集合 X, Y を考える．任意の x ∈ X − Y に対して，Y ∪ {x} が線形独立ではないと仮定する．このとき，hY ∪ Xi = hY i が成り立つことを証明せよ．(注：問題 2.3 を用いてもよい．) 追加問題 2.6 次に挙げる，有限集合 E = {1, 2, 3, 4} 上の有限集合族 I はマトロイドではない．なぜマトロイドではないのか説明せよ． 1. I = {∅, {1}, {2}, {3}, {4}, {1, 3}, {2, 4}}. 2. I = ∅. 追加問題 2.7 自然数 n ≥ 1, r ≥ 0 に対して一様マトロイド Ur,n の独立集合の数は何であるか？ n と r から簡単に計算できる公式を導け．(注：もちろん「簡単に」という判断は主観でよい．) 1