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}}$.