<p>from <a href="/ja/%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89">マトロイド</a>
2部グラフの最大マッチングは，分割マトロイド対のマトロイド交叉
<img src="https://gyazo.com/a370998bd984fe19e25da836e8ab653f/thumb/1000" alt="image"></p>
<ul>
<li>V1側頂点に注目すると、一つの頂点からは高々1本の辺しか出ない<ul>
<li>つまり<a href="/ja/%E5%88%86%E5%89%B2%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89">分割マトロイド</a></li>
</ul>
</li>
<li>V2側も同様</li>
<li>マッチングである辺集合はこの二つの共通部分集合<ul>
<li>つまり<a href="/ja/%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89%E4%BA%A4%E5%8F%89">マトロイド交叉</a></li>
</ul>
</li>
</ul>
<p><a href="https://app.mathsoc.jp/meeting_data/tokyo18mar/pdf/msjmeeting-2018mar-00f004.pdf">https://app.mathsoc.jp/meeting_data/tokyo18mar/pdf/msjmeeting-2018mar-00f004.pdf</a></p>
<ul>
<li><a href="/ja/%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89%E4%BA%A4%E5%8F%89">マトロイド交叉</a></li>
<li><a href="/ja/%E5%A2%97%E5%8A%A0%E9%81%93%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0">増加道アルゴリズム</a></li>
<li><a href="/ja/2%E9%83%A8%E3%82%B0%E3%83%A9%E3%83%95">2部グラフ</a>上の<a href="/ja/%E6%9C%80%E5%A4%A7%E3%83%9E%E3%83%83%E3%83%81%E3%83%B3%E3%82%B0">最大マッチング</a>問題は，<a href="/ja/%E5%88%86%E5%89%B2%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89">分割マトロイド</a>対の交叉問題</li>
</ul>
