2部グラフの最大マッチングは，分割マトロイド対のマトロイド交叉
from マトロイド
2部グラフの最大マッチングは，分割マトロイド対のマトロイド交叉
https://gyazo.com/a370998bd984fe19e25da836e8ab653f
V1側頂点に注目すると、一つの頂点からは高々1本の辺しか出ない
つまり分割マトロイド
V2側も同様
マッチングである辺集合はこの二つの共通部分集合
つまりマトロイド交叉
https://app.mathsoc.jp/meeting_data/tokyo18mar/pdf/msjmeeting-2018mar-00f004.pdf
マトロイド交叉
増加道アルゴリズム
2部グラフ上の最大マッチング問題は，分割マトロイド対の交叉問題