マトロイドのお勉強メモ - Combinatorial Optimization Fifth Edition

下書きにあったので雑に放流することにする。岡山はいいところでした。

-----------------------

岡山の数物セミナー spmAd3rd に備えて Combinatorial Optimization の 13 章 Matroids を読む。東京大学に所属しているので無料で PDF が落とせる、良い話。分かりにくいところがあったらここにメモする。
電気通信大学の授業スライドが分かりやすい日本語資料として紹介されたのでこれを適宜活用。

定義まとめ

$r \left( X \right)$ : $\max\{|Y| : Y \subseteq X, Y \in \mathcal{F}\}$
$\sigma \left( X \right)$ : $\{y \in E : r \left( X \cup \{ y \} \right) = r \left( X \right) \}$ 要は入れても $r$ が変わらない要素からなる集合。
$\rho \left( X \right)$ : $\min\{|Y| : Y \subseteq X, Y \in \mathcal{F}$ かつ任意の $x \in X \ \setminus Y$ に対して $Y \cup \{x\} \notin \mathcal{F}$ となる $\}$
$q \left( E, \mathcal{F} \right)$ : $\min_{F \subseteq E} \frac{\rho \left( F \right)}{r \left(F\right)}$
$\mathcal{F}^*$ : $\{ F \subseteq E : F \cap B = \emptyset$ となる $\left( E, \mathcal{F} \right)$ の base $B$ が存在する $\}$ マトロイドの双対の定義。

13.1 Independence Systems and Matroids

P321

circuits, bases, bases of $X$ あたりの話が分かりにくかった。整理すると

base: $B \in \mathcal{F}$ で任意の $e \in E \ \setminus B$ に対して $B \cup \{e\} \notin \mathcal{F}$ となるもの
circuit: $C \notin \mathcal{F}$ で任意の $e \in C$ に対して $C \ \setminus {e} \in \mathcal{F}$ となるもの
base of $X$ : $B_X \subseteq X, B_X \in \mathcal {F}$ で任意の $e \in X \ \setminus B_X$ に対して $B_X \cup \{e\} \notin \mathcal{F}$ となるもの

で、こいつらからなる集合をそれぞれ bases, circuits, bases of $X$ としている。電気通信大学第3回スライドがかなり分かりやすかった。

P324

Theorem 13.5. の By (M3''), ... の文章が分かりにくかった。 $X,Y \in \mathcal{F}$ なのだから $X$ は base of $X$ である。第3回スライドのP44の絵を見ると分かりやすいが、 $X \subseteq X \cup Y$ なので base of $X \cup Y$ を一つ $B_{X \cup Y}$ として取れば、 $|X| \leq |B_{X \cup Y}|$ となる。これと $|Y| \lt |X|$ と仮定 (M3'') より示される。この文章より後の議論は straightforward なので良い。

13.2 Other Matroid Axioms

P326

Theorem 13.9. の Namely, ... の文章の下にある1行の式が分かりにくかった。左辺が $|B_2|$ に等しくなるのは絵を書くと分かりやすい。後半の不等号は $B_2 \cap \left( X \ \setminus Y \right) = \emptyset$ と $X \subseteq B_1$ より $X \ \setminus Y \subseteq B_1 \ \setminus B_2$ となるので示せる。その先は上の式の左辺と右辺から $|B_1 \cap B_2|$ を引いてあげれば見えやすい。

Theorem 13.10. の A can be ... の文章が(文法的にも)分かりにくかった。 $X \ \setminus Y$ の base を $B$ とすると $\left( X \cap Y \right) \cap \left( X \ \setminus Y \right) = \emptyset$ と $A \subseteq \left( X \cap Y \right), B \subseteq \left( X \ \setminus Y \right)$ なので $A \cap B = \emptyset$ となる。 $C$ は $A \cup B$ に何かつけて $X \cup Y$ の base にしようという感じなので $A,B,C$ はどの $2$ つをとっても共通部分を持たない。
よって so 以下の式が成立する。

P327

Theorem 13.10. の続き。 (R2') から $r \left(X\right) \leq |X|$ を示しているが、これは $\emptyset$ から $1$ つ要素を追加していくごとに $r$ は高々 $1$ しか増えないので示される。

Theorem 13.11. の (S2) を示すところ。 $r\left(\left(X \cup \{ z\}\right)\cap Y\right) \geq r \left(X\right)$ を示したいが、これは $z$ が $Y$ の外、 $Y$ の中かつ $X$ の外、 $X$ の中の $3$ パターンのどれかであり、どれでも $X \subseteq Y$ なので $\left(X \cup \{z\}\right)\cap Y$ は $X$ か $X \cup \{ z\}$ になる。これと $\sigma$ の定義より良い。

13.4 The Greedy Algorithm

P336

Theorem 13.21. のまず主張のところの話。 $F \in \mathcal{F}$ の incidence vector $x$ は $|E|$ 次元ベクトルで、 $e \in E$ について、 $x$ の $e$ 成分は $e \in F$ のとき $1$ で、そうでないとき $0$ となるもの。
その下の Proof. 始まってすぐの式の $cx$ とは $\sum_{e \in E} c \left(e\right) x_e$ のこと。