Editing Greedoid (section)

==Examples==
[[File:Vertex search greedoid.svg|thumb|380px|Vertex search greedoid]]
*Consider an undirected [[Graph (discrete mathematics)|graph]] {{mvar|G}}.  Let the ground set be the edges of {{mvar|G}} and the feasible sets be the edge set of each ''forest'' (i.e. subgraph containing no cycle) of {{mvar|G}}. This set system is called the '''cycle matroid'''. A set system is said to be a [[graphic matroid]] if it is the cycle matroid of some graph. (Originally cycle matroid was defined on '''circuits''', or minimal ''dependent sets''. Hence the name cycle.)
*Consider a finite, undirected graph {{mvar|G}} [[rooted graph|rooted]] at the vertex {{mvar|r}}. Let the ground set be the vertices of {{mvar|G}} and the feasible sets be the vertex subsets containing {{mvar|r}} that induce connected subgraphs of {{mvar|G}}. This is called the '''vertex search greedoid''' and is a kind of antimatroid.
*Consider a finite, [[directed graph]] {{mvar|D}} rooted at {{mvar|r}}.  Let the ground set be the (directed) edges of D and the feasible sets be the edge sets of each directed subtree rooted at {{mvar|r}} with all edges pointing away from {{mvar|r}}.  This is called the '''line search greedoid''', or '''directed branching greedoid'''.  It is an interval greedoid, but neither an antimatroid nor a matroid.
*Consider an {{math|''m'' × ''n''}} [[Matrix (mathematics)|matrix]] {{mvar|M}}.  Let the ground set {{mvar|E}} be the indices of the columns from 1 to {{mvar|n}} and the feasible sets be <math display=block>F = \{X \subseteq E: \text{ submatrix } M_{\{1,\ldots,|X|\},X} \text{ is an invertible matrix}\}.</math> This is called the '''Gaussian elimination greedoid''' because this structure underlies the [[Gaussian elimination]] algorithm.  It is a greedoid, but not an interval greedoid.