Matroide/Einführung/Textabschnitt

Definition

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

Die dritte Eigenschaft heißt dabei die Austauscheigenschaft. Sie besagt, dass man jede Menge ${}B$, die zu dem Matroid gehört, zu einer größeren Menge des Matroids mit Hilfe eines Elements von ${}A$ auffüllen kann, sobald ${}A$ mehr Elemente als ${}B$ besitzt und ebenfalls zum Matroid gehört. Das folgende Standardbeispiel für ein Matroid ist aus der linearen Algebra bekannt.

Beispiel

Es sei ${}V$ ein ${}K$-Vektorraum und sei ${}v_{i}$, ${}i\in I$, eine Familie von Vektoren in ${}V$ zu einer endlichen Indexmenge ${}I$. Wir setzen

${\mathcal {M}}={\left\{J\subseteq I\mid {\text{Die Familie }}v_{j},j\in J,{\text{ ist linear unabhängig}}\right\}}\,$

und behaupten, dass es sich dabei um ein Matroid handelt. Die Eigenschaften ergeben sich aus Fakt  (1,2) und aus folgender Überlegung: Wenn die Teilfamilien ${}v_{j}$, ${}j\in J$ und ${}v_{\ell }$, ${}\ell \in L$ zu ${}J,L\subseteq I$ jeweils linear unabhängig sind, und ${}L$ ein Element mehr als ${}J$ besitzt, so gilt für die erzeugten Untervektorräume aus Dimensionsgründen

${}\langle v_{\ell },\ell \in L\rangle \not \subseteq \langle v_{j},j\in J\rangle \,.$

Daher gibt es auch ein ${}v_{k}$, ${}k\in L$, mit ${}v_{k}\notin \langle v_{j},j\in J\rangle$. Doch dann ist die erweiterte Familie ${}v_{j},j\in J,v_{k}$ ebenfalls linear unabhängig.

Wegen dieses Beispiels nennt man die Mengen aus ${}E$, die zu einem Matroid gehören, die unabhängigen Mengen. Die folgende Terminologie orientiert sich ebenfalls an der linearen Algebra.

Definition

In einem Matroid ${}{\mathcal {M}}$ auf einer Menge ${}I$ nennt man die maximalen Mengen aus ${}{\mathcal {M}}$ Basen.

Ein ${}B\in {\mathcal {M}}$ ist also genau dann eine Basis, wenn keine Teilmenge ${}A\subseteq I$ mit ${}B\subset A$ zu ${}{\mathcal {M}}$ gehört. Aufgrund der Austauscheigenschaft besitzt jede Basis in einem Matroid die gleiche Anzahl.

Definition

In einem Matroid ${}{\mathcal {M}}$ auf einer Menge ${}I$ nennt man die gemeinsame Anzahl der Elemente in einer jeden Basis von ${}{\mathcal {M}}$ den Rang des Matroids.