Matroid/Definition

Matroid

Zu einer endlichen Menge ${}E$ heißt eine Teilmenge

${}{\mathcal {M}}\subseteq {\mathfrak {P}}\,(E)\,$

ein Matroid, wenn folgende Bedingungen erfüllt sind.

1. Es ist  ${}\emptyset \in {\mathcal {M}}$. 
2. Aus  ${}A\in {\mathcal {M}}$  und  ${}B\subseteq A$  folgt  ${}B\in {\mathcal {M}}$. 
3. Wenn  ${}A,B\in {\mathcal {M}}$  mit

   ${}{\#\left(A\right)}={\#\left(B\right)}+1\,,$

   so gibt es ein  ${}a\in A\setminus B$  derart, dass  ${}B\cup \{a\}\in {\mathcal {M}}$.