Matroide/Einführung/Textabschnitt

Aus Wikiversity


Definition  

Zu einer endlichen Menge heißt eine Teilmenge

ein Matroid, wenn folgende Bedingungen erfüllt sind.

  1. Es ist .
  2. Aus und folgt .
  3. Wenn mit

    so gibt es ein derart, dass .

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


Beispiel  

Es sei ein -Vektorraum und sei , , eine Familie von Vektoren in zu einer endlichen Indexmenge . Wir setzen

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 , und , zu jeweils linear unabhängig sind, und ein Element mehr als besitzt, so gilt für die erzeugten Untervektorräume aus Dimensionsgründen

Daher gibt es auch ein , , mit . Doch dann ist die erweiterte Familie ebenfalls linear unabhängig.


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


Definition  

In einem Matroid auf einer Menge nennt man die maximalen Mengen aus Basen.

Ein ist also genau dann eine Basis, wenn keine Teilmenge mit zu gehört. Aufgrund der Austauscheigenschaft besitzt jede Basis in einem Matroid die gleiche Anzahl.


Definition  

In einem Matroid auf einer Menge nennt man die gemeinsame Anzahl der Elemente in einer jeden Basis von den Rang des Matroids.