eine Abstraktion des Begriffs einer Matrix im kombinatorischen Sinne.

Es sei V eine endliche Menge. Ein Matroid ist ein Tupel \((V,{\mathscr{S}})\), wobei \({\mathscr{S}}\) ein System von Teilmengen von V, genannt die unabhängigen Teilmengen, mit folgender Eigenschaft bezeichnet:

• Die leere Menge ist unabhängig.

• Jede Teilmenge einer unabhängigen Menge ist unabhängig.

• Sind S₁ und \({S}_{2}\in {\mathscr{S}}\) mit |S₁| = |S₂| + 1, so existiert ein s ∈ S₁ \ S₂ mit \({S}_{2}\cup \{s\}\in {\mathscr{S}}\).