マトロイド
https://gyazo.com/51f048871eb1073c9644717dffee67ff
ある集合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 交換則
https://gyazo.com/6f54763518ea15189443285f8a86a521
任意のxではないことに注意
それ以上要素を追加することのできない極大独立集合(基)はどれも同じサイズである
例
ベクトルの集合Eと、一次独立なベクトルの集合の族F
A2: 一次独立なベクトルの一部を取ったものは一次独立
A3: 次数の高い空間Yの中にはXと一次独立なベクトルがある
要素数一定以下の集合の族
一様マトロイド
このページの冒頭の図は要素数2以下の一様マトロイド
分割マトロイド
Eをいくつかの集合に分割してその中から高々1個の要素を選んだもの
https://gyazo.com/c57edc9c7c64462d160d86b1a8f21fdb
無向グラフの辺集合Eと閉路のないF(森)
閉路マトロイド
マトロイドに対する貪欲法
abc137d
マトロイドに対する貪欲法
意外と詳しい