マトロイド
E を体上の行列の列集合、その体上で線形独立である列の集合を F とするとき、(E, F) はマトロイドとなり、ベクトルマトロイド (vector matroid) と呼ぶ。マトロイドが同等の体 K 上のベクトルマトロイドとして記述できるとき、表現可能であると呼ばれる。任意の体上で表現可能なマトロイドを正則マトロイド (regular matroid) と呼び、位数2の有限体上で表現可能なマトロイドを2値マトロイド(英語版) (binary matroid) と呼ぶ。これらは、
マトロイド ⊃ 2値マトロイド ⊃ 正則マトロイド ⊃ グラフ的マトロイド
という包含関係が成り立つ。一方で、Fanoマトロイドは、2値マトロイドであるが(実数体上では表現できないため)正則マトロイドではない。また、Vámosマトロイド(英語版) (Vámos matroid) は、任意の体上で表現できないマトロイドの最も簡単な例である。
例えば、 E = {1, 2, 3}, F = {{1}, {2}, {1,2}} というマトロイドに対して基の族 B = { {1, 2} } だから F = { {3} } となる。双対のランク関数も、例えば r({1, 3}) = 2 + r({2}) - r({1, 2, 3}) = 2 + 1 - 2 = 1 となるように、成り立っていることが分かる。
また、平面グラフに対する双対とグラフ的マトロイドの双対の概念は一致する。つまり、任意の平面的グラフ G の閉路マトロイド M(G) の双対は、G の双対平面グラフ G のマトロイドと(平面埋め込みの方法によらず)同一である。
マトロイドにおいては貪欲法で最適解が得られることを示す。なお、マトロイドの貪欲法は組合せ最適化の貪欲法の全てを網羅しているわけではない。たとえば、クラスカル法はマトロイド上の貪欲法で説明できるが、プリム法やダイクストラ法は異なる。
独立性システム (E, F) とコスト関数 c : E → R + {\displaystyle c:E\to \mathbb {R} _{+}} に対する最小化問題を解く。最悪棄却貪欲法は、都合の悪い e ∈ E を優先して解から除外する。つまり、
c ( e 1 ) ≥ c ( e 2 ) ≥ ⋯ ≥ c ( e n ) {\displaystyle c(e_{1})\geq c(e_{2})\geq \cdots \geq c(e_{n})} となるように E = { e 1 , e 2 , ⋯ , e n } {\displaystyle E=\{e_{1},e_{2},\cdots ,e_{n}\}} をソートする。
E a n s ← E {\displaystyle E_{ans}\leftarrow E}
For i = 1 to n : E a n s ∖ { e i } {\displaystyle E_{ans}\setminus \{e_{i}\}} が基を含むならば、 E a n s ← E a n s ∖ { e i } {\displaystyle E_{ans}\leftarrow E_{ans}\setminus \{e_{i}\}}