マトロイド

• ある集合Eの部分集合の族Fが都合のいい性質を満たす時に、(E, F)をマトロイドと言う
• マトロイド上の最大化であれば、貪欲法で最適解が得られる
• Fに含まれている部分集合を「独立である」という
• Fは基本的に全列挙しない(それでは全探索と同じオーダーになるから)
  • かわりにある部分集合がFに含まれるかどうかを返す関数「独立性オラクル」が定義できればよい

定義

• A1: $\emptyset \in F$
• A2: $X \in F \Rightarrow \forall (Y \subset X) Y \in F$
  • Hereditary 遺伝性
  • XがFに入ってるならXの部分集合も全部入ってる
• A3: $X,Y \in F, |X| < |Y| \Rightarrow \exists x, x \in Y, x \notin X, X + {x} \in F$
  • Yの方が大きいなら、一つ選んでXに追加することができる
  • Exchange Property 交換則
  • 
  • 任意のxではないことに注意

それ以上要素を追加することのできない極大独立集合(基)はどれも同じサイズである

例

• ベクトルの集合Eと、一次独立なベクトルの集合の族F
  • A2: 一次独立なベクトルの一部を取ったものは一次独立
  • A3: 次数の高い空間Yの中にはXと一次独立なベクトルがある
• 要素数一定以下の集合の族
  • 一様マトロイド
  • このページの冒頭の図は要素数2以下の一様マトロイド
• 分割マトロイド
  • Eをいくつかの集合に分割してその中から高々1個の要素を選んだもの
  • 
• 無向グラフの辺集合Eと閉路のないF(森)
  • 閉路マトロイド
• 無向グラフの辺集合E、Fがpseudoforest
  • Bicircular matroid - Wikipedia

マトロイド交叉 2部グラフの最大マッチングは，分割マトロイド対のマトロイド交叉

マトロイドに対する貪欲法

abc137d https://img.atcoder.jp/abc137/editorial.pdf マトロイドに対する貪欲法 最小費用流に帰着

https://ja.m.wikipedia.org/wiki/マトロイド 意外と詳しい

https://app.mathsoc.jp/meeting_data/tokyo18mar/pdf/msjmeeting-2018mar-00f004.pdf

• マトロイド交叉
• 増加道アルゴリズム
• 2部グラフ上の最大マッチング問題は，分割マトロイド対の交叉問題
  • 二部グラフの最大マッチングと増加道 | 高校数学の美しい物語
• 主双対アルゴリズム
  • Primal-dual

http://www.ieice-hbkb.org/files/12/12gun_02hen_05.pdf

https://drken1215.hatenablog.com/entry/20121212/1355280288 https://maspypy.com/atcoder-jsc2019予選-e-card-collector-（マトロイド）