グリードイド
有限集合 E {\displaystyle E} とその部分集合族 F ⊆ 2 E {\displaystyle F\subseteq 2^{E}} の組 ( E , F ) {\displaystyle (E,F)} が
(A1) ∅ ∈ F {\displaystyle \emptyset \in {F}}
(A3) X , Y ∈ F , | X | > | Y | ⇒ ∃ x ∈ X ∖ Y s.t. Y ∪ { x } ∈ F . {\displaystyle X,Y\in F,\ |X|>|Y|\Rightarrow \exists \ x\in X\setminus Y{\text{ s.t. }}Y\cup \{x\}\in F.}
を満たすとき、グリードイドと呼ぶ。
Gをグラフ、Gのある頂点を r ∈ V ( G ) {\displaystyle r\in V(G)} とする。E=E(G)、Fをrを根とするグラフGの(全点でなくともよい)すべての木とする。このとき、(E,F)はグリードイドであり、Gの根付き森グリードイド(branching greedoid)と呼ぶ。根付き森グリードイドは、グリードイドであるが、マトロイドではない。実際、rを含む森の部分森が必ずしもrを含むとは限らないことは明らかである。