はじめに
ISer Advent Calendar 2021 - Adventarの記事として書かれました．*1
授業で扱わなかったけど，ちゃんと知っておきたいなということで記事にしようと思った．ちゃんと読みたい人は下に載せた参考文献を読んでくれー
マトロイド
マトロイドの定義
マトロイドとは，有限集合 $E$ に対して，有限集合族 $\mathcal{I}\subseteq 2^{E}$ が次を満たすとき，$\mathcal{I}$ はマトロイドという．
- $\emptyset \in \mathcal{I} $
- $X\in \mathcal{I}\land Y \subseteq X $ ならば， $Y\in\mathcal{I}$
- $X,Y\in \mathcal{I}\land |X|>|Y| $ ならば，$ \exists e\in X-Y~s.t.~Y\cup\{e\}\in \mathcal{I} $
このほかにも同値な定義の方法があるのですが，割愛します．
マトロイドの交わり
ここで，マトロイドの交わりを次のように定義する． $\mathcal{I}_1, \mathcal{I}_2$ をマトロイドとする．次の集合をマトロイドの交わりと呼ぶ．
\begin{align} \mathcal{I}_1\cap \mathcal{I}_2 = \{X| X\in \mathcal{I}_1, X\in \mathcal{I}_2 \} \end{align}
これはマトロイドになるとは限らない．
\begin{align} E &= \{1,2,3,4\}\\ \mathcal{I}_1 &= \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\} \}\\ \mathcal{I}_2 &= \{\emptyset, \{1\}, \{2\},\{3\}, \{4\}, \{1,2\}, \{1,3\}, \{1,4\} \}\\ \mathcal{I}_1\cap \mathcal{I}_2 &= \{\emptyset, \{1\}, \{2\},\{3\},\{1,2\}\} \end{align}
上において，交わりの $\{3\}, \{1,2\}$ にマトロイドの3つ目の定義が成り立たない．
分割マトロイド
次の部分集合族はマトロイドになり，分割マトロイドと呼ぶ．
$E$を有限集合として，$E$ の分割 $\{E_1,E_2,E_3,\dots, E_n \}$ と自然数列 $r_1,\dots, r_n\geq 0$ を考える． この時，次の $\mathcal{I}$ を分割マトロイドと呼ぶ．
\begin{align} \mathcal{I} = \{X\subseteq E | \forall i \in\{1,\dots, n\}.~|X\cap E_i|\leq r_i \} \end{align}
マトロイドになることの証明
分割に関して帰納的に証明する． $\mathcal{I}_1,\mathcal{I}_2$をそれぞれdisjointな有限集合$E_1,E_2$上のマトロイドとする．この時， $\mathcal{I}_1\oplus \mathcal{I}_2=\{X_1\cup X_2 | X_1\in\mathcal{I}_1, X_2\in\mathcal{I}_2 \}$ は$E_1\cup E_2$ 上のマトロイドとなる．
- $\emptyset$ は$\emptyset\in \mathcal{I}_1,\emptyset\in \mathcal{I}_2$より， $\emptyset \in \mathcal{I}_1\oplus \mathcal{I}_2$
よって，1つ目の性質は示された．
- $X\in\mathcal{I}_1\oplus \mathcal{I}_2$として，$Y\subseteq X$ とする．
- この時，$E_1,E_2$は互いにdisjointな集合であるので，$X=X_1\cup X_2, ~(X_1\in E_1, X_2\in E_2)$ が存在する．
- 同様に，$Y=Y_1\cup Y_2 ~(Y_1\in E_1, Y_2\in E_2)$が存在する．
- $E_1,E_2$は互いにdisjointな集合であるので，$Y\subseteq X$ より $Y_1\subseteq X_1, Y_2\subseteq X_2$が成り立つ．
- $\mathcal{I}_1,\mathcal{I}_2$はそれぞれマトロイドであるため，$Y_1\in E_1, Y_2\in E_2$が成り立つ．したがって，$Y=Y_1\cup Y_2 \in \mathcal{I}_1\oplus \mathcal{I}_2$である．
2つ目の性質は示された．
- $X,Y\in\mathcal{I}_1 \oplus \mathcal{I}_2$ として，$|Y|<|X|$ とする．この時，先ほどと同様の議論より，$X_1,X_2, Y_1, Y_2$が存在し，$X_1,Y_1\in\mathcal{I}_1, X_2,Y_2\in\mathcal{I}_2$を満たす．
- $E_1,E_2$は互いにdisjointな集合より，$|Y|=|Y_1|+|Y_2|, |X|=|X_1|+|X_2|$ が成り立つ．
- $|Y|<|X|$ より， $|X_1|>|Y_1|$ または $|X_2|>|Y_2|$のどちらかは成り立つ．ここでは $|X_1|>|Y_1|$ が成り立つとする．
- マトロイド$\mathcal{I}_1$の3つ目の定義より，$e\in X_1 - Y_1$が存在し，$Y_1\cup \{e\}\in\mathcal{I}_1$である．
- 以上より，$e\in (X_1\cup X_2) - (Y_1\cup Y_2)$であり，$(Y_1\cup Y_2)\cup\{e\}\in\mathcal{I}_1\oplus \mathcal{I}_2$が成り立つ．
3つ目の性質が示された．
以上より，$\mathcal{I}_1\oplus \mathcal{I}_2$はマトロイドである．この直和を帰納的に使えば，分割マトロイドはマトロイドであることがわかる．
マトロイドによる2部グラフの最大マッチングのモデル化
二部グラフの最大マッチングとは，次の問題である．
グラフ $G$ について頂点集合$V=V_1\cup V_2$，辺集合$E$とする． 問題は，$E$ の部分集合であって端点を共有することはない最大の部分集合を見つけることである．
この問題を言い換えると，$V_1, V_2$ それぞれにおいて各頂点は高々1つの辺にしか接続しないという制約の下での最大共通部分集合である．
$\delta(u)$は頂点$u$に接続する辺集合を表すとする．$V_1, V_2$に関する制約を定式化すると，
\begin{align} \mathcal{I}_1 = \{X\subseteq E | | X\cup \delta(u)|\leq 1~(u \in V_1) \}\\ \mathcal{I}_2 = \{X\subseteq E | | X\cup \delta(u)|\leq 1~(u \in V_2) \} \end{align}
となり，上は分割マトロイドである．
2部グラフの最大マッチングは，マトロイドの交わりを用いて，$\max |X| s.t. X \in \mathcal{I}_1\cap \mathcal{I}_2$と表すことができる．
おわりに
リファレンスならともかく何かを参考にしてまとめることはあんまり好きではない．
参考文献
離散最適化基礎論 (2015年度後学期) 組合せ最適化におけるマトロイドの役割 http://bigdata.nii.ac.jp/eratokansyasai3/wp-content/uploads/2016/09/0810_10_kakimura.pdf
*1:大遅刻
