2部グラフの最大マッチングは，分割マトロイド対のマトロイド交叉
from マトロイド
2部グラフの最大マッチングは，分割マトロイド対のマトロイド交叉
V1側頂点に注目すると、一つの頂点からは高々1本の辺しか出ない
つまり分割マトロイド
V2側も同様
マッチングである辺集合はこの二つの共通部分集合
つまりマトロイド交叉
Related Pages
- →chokudai×貪欲法の証明パターン×選択肢が少ない方から貪欲×マトロイド×クラスカル法×区間スケジューリング×交換しても悪化しない×アルゴリズムとデータ構造×区間はマトロイドではない×abc076b×現在が良いほど未来も良い×poj3617×poj3069×ダイクストラ法×agc009a×arc111×abc187×arc110c×一回り小さい同じ形の問題×agc049b×abc103d×abc023d×和の比率の最大化×単位時間ジョブスケジューリング問題×乱択＋貪欲×abc171_f×離散凸性→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]