- ある集合Eの部分集合の族Fが都合のいい性質を満たす時に、(E, F)をマトロイドと言う
- マトロイド上の最大化であれば、貪欲法で最適解が得られる
- Fに含まれている部分集合を「独立である」という
- Fは基本的に全列挙しない(それでは全探索と同じオーダーになるから)
- かわりにある部分集合がFに含まれるかどうかを返す関数「独立性オラクル」が定義できればよい
定義
- A1:
- A2:
- Hereditary 遺伝性
- XがFに入ってるならXの部分集合も全部入ってる
- A3:
- Yの方が大きいなら、一つ選んでXに追加することができる
- Exchange Property 交換則
- 任意のxではないことに注意
それ以上要素を追加することのできない極大独立集合(基)はどれも同じサイズである
例
- ベクトルの集合Eと、一次独立なベクトルの集合の族F
- A2: 一次独立なベクトルの一部を取ったものは一次独立
- A3: 次数の高い空間Yの中にはXと一次独立なベクトルがある
- 要素数一定以下の集合の族
- 一様マトロイド
- このページの冒頭の図は要素数2以下の一様マトロイド
- 分割マトロイド
- Eをいくつかの集合に分割してその中から高々1個の要素を選んだもの
- 無向グラフの辺集合Eと閉路のないF(森)
- 閉路マトロイド
- 無向グラフの辺集合E、Fがpseudoforest
マトロイド交叉 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
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-(マトロイド)