マトロイド
c ( G ) ≥ q ( E , F ) c ( O P T ) {\displaystyle c(G)\geq q(E,F)c(OPT)} の証明の概要を述べる。
G を最良選択貪欲法で得られる解、 O P T {\displaystyle OPT} を最適解とする。 E = { e 1 , ... , e n } {\displaystyle E=\{e_{1},\ldots ,e_{n}\}} は、 c ( e 1 ) ≥ c ( e 2 ) ≥ ⋯ ≥ c ( e n ) {\displaystyle c(e_{1})\geq c(e_{2})\geq \cdots \geq c(e_{n})} となるようにソート済みであるとし、 E j = { e 1 , ... , e j } {\displaystyle E_{j}=\{e_{1},\ldots ,e_{j}\}} とする。また、
d j = { c ( e n ) , if j = n c ( e j ) − c ( e j + 1 ) , otherwise {\displaystyle d_{j}={\begin{cases}c(e_{n}),&{\mbox{if }}j=n\\c(e_{j})-c(e_{j+1}),&{\mbox{otherwise}}\end{cases}}}
q ( E , F ) := min X ⊆ E ρ ( X ) r ( X ) {\displaystyle q(E,F):=\min _{X\subseteq {E}}{\frac {\rho (X)}{r(X)}}}
マトロイドのとき q ( E , F ) = 1 {\displaystyle q(E,F)=1} である。独立性システムのとき q ( E , F ) ≤ 1 {\displaystyle q(E,F)\leq 1} であり、 A ∈ F , b ∈ E {\displaystyle A\in F,b\in E} に対して A ∪ { b } {\displaystyle A\cup \{b\}} が高々p 個しかサーキットを持たないならば 1 / p ≤ q ( E , F ) {\displaystyle 1/p\leq q(E,F)} であることが知られているのでランク商を見積もることが可能である。
E を無向グラフGの辺集合、F を森の集合とするとき、(E, F) はマトロイドとなり、グラフ的マトロイド(英語版) (graphic matroid) または 閉路マトロイド (cycle matroid) と呼ぶ。しばしばグラフGがグラフ的マトロイドであることを M(G) と書く。グラフ的マトロイドにおける従属集合は、閉路を持つグラフの集合であるから、サーキットとは単純閉路となる辺集合である。また(X の)基とは(X の部分集合の中で)できうる最大の森のことで、明らかに(X でカバーされる)点の数 − 1 本の辺で作られる森が最大であり、この森の集合を言う。よって、階数関数は r(X) = (Xがカバーする点数) − 1 と書ける。
他にも、グラフにおけるマトロイドはいくつか知られている。
E を無向グラフ G の辺集合、F を (G, X) がpseudoforest(英語版)となるようなXの集合とするとき (E, F) はマトロイドとなる。これを、bicircularマトロイド(英語版) (bicircular matroid) と呼ぶ。
点集合 U, V、辺集合 X とする2部グラフ G = (U, V, X) において、マッチングの端点となる点集合 S ⊆ U {\displaystyle S\subseteq U} を要素とする集合をFとするとき、(U, F) はマトロイドとなる。これを、横断マトロイド (transversal matroid) と呼ぶ。完全2部グラフ K n , r {\displaystyle K_{n,r}} の横断マトロイドは、一様マトロイド U n r {\displaystyle U_{n}^{r}} である。
点集合を V とするグラフにおいて、点の部分集合を V ′ , U ⊆ V {\displaystyle V',U\subseteq V} とする。U への点素な |U| 本の道が存在する V' の部分集合を F の要素とすると、(V', F) はマトロイドとなる。これを、ガンモイド(英語版) (gammoid) と呼ぶ。特に、(V, F) を狭義ガンモイド (strict gammoid) と呼ぶ。