Matroid

Ein Matroid (n.) ist eine mathematische Struktur mit deren Hilfe der Begriff der (linearen) Unabhängigkeit verallgemeinert wird. Matroide sind in vielen Bereichen der Kombinatorik (z. B. kombinatorischen Optimierung, diskrete kombinatorische Geometrie u. a.), aber auch in anderen Bereichen wie der Graphentheorie bedeutsam. In vielen Fällen werden allerdings orientierte Matroide benötigt, die gegenüber den "gewöhnlichen" Matroiden qualitativ deutlich mehr Information tragen.

Definition

Ein Matroid über einer Menge $E$ ist ein Paar $M=(E,U)$ mit $U \subseteq \mathcal P(E)$ (d.h. $U$ ist eine Teilmenge der Potenzmenge von $E$), die folgende Bedingungen erfüllt:

1. $\emptyset \in U$
2. $A \subset B, B\in U \Rightarrow A \in U$
3. $A, B\in U$ und $\left| A \right| < \left| B\right| \Rightarrow \exists x \in B \setminus A$mit $A \cup \{x\} \in U$
4. $\exists n\in\mathbb N_0$ mit $|A|\leq n$ für alle $A\in U$,

wobei $\left| A \right|$ die Kardinalität der Menge $A$ bezeichnet. Die Elemente von $E$ nennt man auch die Elemente (oder Punkte) des Matroids, die Elemente von $U$ die unabhängigen Teilmengen von $(E,U)$ (anderenfalls heißen die Mengen abhängig). Falls das Paar $(E,U)$ nur die ersten beiden Bedingungen erfüllt, wird es als Unabhängigkeitssystem bezeichnet. Die dritte Bedingung wird oft auch als Austauscheigenschaft oder Austauschaxiom bezeichnet. Die vierte Bedingung ist offenbar in endlichen Mengen E trivial. Das kleinste n, für das diese erfüllt ist, nennt man den Rang von M.

Austauscheigenschaft

Das Kennzeichnende eines Matroids gegenüber einem "gewöhnlichen" Unabhängigkeitssystem besteht in der Austauscheigenschaft. Während sich die Bedingungen 1. und 2. verhältnismäßig leicht als Abgeschlossenheit der Menge U hinsichtlich des Teilmengen-Operators verstehen lassen, so ist die Motivation der Austauscheigenschaft weniger offensichtlich. Man kann sich diese wie folgt veranschaulichen: Durch $|B \backslash A|$-fache Anwendung der Austauscheigenschaft kann man $|B \backslash A|$ Elemente aus B zu A hinzufügen. Weshalb man anstatt von der Austauscheigenschaft teilweise auch von der augmentation-property („Vergrößerungseigenschaft“) spricht. Von der so erzeugten Menge weiß man, dass sie ebenfalls Element des Unabhängigkeitssystems U ist. Diese Menge enthält nun zwar Elemente aus B, allerdings wurden im Vergleich zu B $|A\backslash B|$-viele Elemente durch Elemente aus $A \backslash B$ ausgetauscht. Dies begründet den Namen Austauscheigenschaft.

Beispiele

1. Sei $E$ eine endliche Menge von Vektoren (z. B. die Spalten einer Matrix, daher auch die Bezeichnung „Matroid‟) und seien die Elemente von $U$ genau die linear unabhängigen Teilmengen von $E$, dann ist $(E, U)$ ein Matroid.
2. Sei $E$ die Kantenmenge eines endlichen Graphen, und $U$ enthalte genau alle kreisfreien Teilmengen von $E$, dann ist $(E, U)$ ein Matroid (auch graphisches Matroid genannt). Die maximalen Elemente von $U$ sind dann die aufspannenden Wälder des zugrundeliegenden Graphen.

Alternative Charakterisierungen eines Matroids

Zu einem Matroid über der Menge $E$ kann man ausgehend von dem System $U$ der unabhängigen Teilmengen weitere Systeme von Kreisen $K$ und Basen $B$ in $E$ definieren sowie einen Hüllenoperator $s\colon \mathcal P(E)\to \mathcal P(E)$ und eine Rangfunktion $r\colon \mathcal P(E)\to \mathbb N_0$ und dafür spezielle Eigenschaften beweisen. Wenn umgekehrt zur Menge $E$ nur ein System $K$, $B$, $s$ oder $r$ mit der jeweiligen speziellen Eigenschaft gegeben ist, kann man dazu ein System $U'$ definieren, das $E$ zu einem Matroid macht.

Definiert man schließlich ausgehend von $U$ zunächst $K$ und dazu $U'$ (und dazu wieder $K'$), so gilt $U=U'$ (und $K=K'$); analog für die Systeme $B$, $s$ und $r$ (Aufzählung ohne Anspruch auf Vollständigkeit).

Kreise

Eine Menge $K \subseteq E$ eines Matroids $(E,U)$ heißt Kreis, wenn gilt $K \notin U$, aber es gilt $K_0 \in U$ für alle $K_0 \subsetneq K$.

Das System $K$ der Kreise des Matroids $(E,U)$ besteht aus den minimalen unter den abhängigen Teilmengen in $\mathcal{P}(E) \setminus U$. Anders ausgedrückt: Eine Teilmenge $A\subseteq E$ ist unabhängig genau dann, wenn sie keinen Kreis enthält (kreisfrei ist): $A \in U \Leftrightarrow \nexists B \in K:B\subseteq A$. Im obigen Beispiel 2 sind die Kreise des Matroids gerade die Kreise des zugrundeliegenden Graphen.

Eigenschaften: Die leere Menge ist kein Kreis. Keine echte Teilmenge eines Kreises ist ein Kreis. Wenn man zwei Kreise (im Beispiel rechts den roten und den grünen) vereinigt und ein Element, das zu beiden Kreisen gehört (im Beispiel die rot-grün gestrichelte Kante), aus der Vereinigung herausnimmt, enthält der Rest noch einen (dritten) Kreis.

Umgekehrt: Hat man zur Menge $E$ ein System $K$ von Kreisen genannten nicht leeren Teilmengen mit diesen Eigenschaften, so bilden die kreisfreien Teilmengen ein System unabhängiger Teilmengen, das $E$ zum Matroid mit Kreissystem $K$ macht.

Basen

Die maximalen Elemente von $U$ bzgl. $\subseteq$ heißen Basen des Matroids. Alle Basen enthalten gleich viele Elemente, diese Anzahl nennt man den Rang $r(U)$ des Matroids. Dieser Begriff von Basis entspricht demjenigen im endlichdimensionalen Vektorraum. Im Beispiel 2 sind die Basen die aufspannenden Bäume.

Eigenschaft: Zu Basen $B_1,B_2$ und $x\in B_1\setminus B_2$ existiert ein $y\in B_2\setminus B_1$, so dass $(B_1\cup\{y\})\setminus\{x\}$ eine Basis ist. Dieser sog. Austauschsatz von Steinitz ist ein wichtiges Beweismittel der linearen Algebra, das zum Beispiel die Festlegung der Dimension eines Vektorraumes ermöglicht.

Umgekehrt: Hat man zur Menge $E$ ein nicht leeres System $B$ von Basen, für das dieser Austauschsatz gilt, so bilden die Teilmengen dieser Basen ein System unabhängiger Teilmengen, das $E$ zum Matroid mit Basensystem $B$ macht.

Rangfunktion

Zu einer Teilmenge $F\subset E$ bilden die in $F$ enthaltenen unabhängigen Mengen das System $U_F = \{A\in U\mid A\subseteq F\}$ und ein Matroid $(F,U_F)$, dessen Rang $r(U_F)$ auch als $r(F)=\max\{|A|\mid A\in U,A\subseteq F\}$ aufgefasst werden kann.

Eigenschaften: Für die so definierte Rangfunktion $r\colon \mathcal P(E)\to \mathbb N_0$ gilt:

• $0\le r(A) \le |A|$
• Aus $A\subseteq B$ folgt $r(A)\le r(B)$
• $r(A) + r(B) \ge r(A\cup B) + r(A\cap B)$

Umgekehrt: Hat man zur Menge $E$ eine Funktion $r$ mit diesen Eigenschaften, so bilden die Teilmengen $A\subseteq E$ mit $r(A)=|A|$ ein System unabhängiger Teilmengen, das $E$ zum Matroid mit Rangfunktion $r$ macht.

Hüllenoperator

Für eine Teilmenge $A\subseteq E$ ist $s(A) = \{x\in E\mid r(A\cup\{x\}) = r(A)\}$.

Eigenschaften: Die ersten drei Eigenschaften charakterisieren einen allgemeinen Hüllenoperator.

• $A\subseteq s(A)$
• Aus $A\subset B$ folgt $s(A)\subseteq s(B)$
• $s(A) = s(s(A))$

Weil $E$ ein Matroid ist, gilt die Zusatzeigenschaft:

• Ist $y\notin s(A)$, aber $y\in s(A\cup\{x\})$, so gilt $x\in s(A\cup\{y\})$.

Umgekehrt: Hat man zur Menge $E$ eine Funktion $s$ mit diesen Eigenschaften, so bilden die Teilmengen $A\subseteq E$ mit $s(A\setminus\{x\})\ne s(A)$ für alle $x\in A$ ein System unabhängiger Teilmengen, das $E$ zum Matroid mit Hüllenoperator $s$ macht.

Greedy-Algorithmen

Ein gewichteter Matroid ist ein Matroid zusammen mit einer Gewichtsfunktion $w \colon E \to \R^+$, die jedem Element ein Gewicht zuordnet. Für diese Matroide berechnen Greedy-Algorithmen stets Basen mit minimalem oder maximalem Gewicht. Ein Beispiel ist der Algorithmus von Kruskal zur Berechnung eines minimalen aufspannenden Waldes eines Graphen. Die unabhängigen Mengen des zugrundeliegenden Matroids sind die Wälder des Graphen (siehe Beispiel 2).

Ein Unabhängigskeitssystem ist genau dann ein Matroid, wenn ein Greedy-Algorithmus zu jeder Gewichtsfunktion immer Basen minimalen oder maximalen Gewichts berechnet.

Literatur

• James Oxley: Matroid Theory. Oxford Mathematics 2004, ISBN 0-19-853563-5.
• Bernhardt Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4. Auflage, Springer, Berlin 2007, ISBN 978-3-540-71843-7.
• Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall Inc., Englewood Cliffs (NJ) 1982, ISBN 0-13-152462-3.
• Jon Lee: A First Course in Combinatorial Optimization. In: Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge 2004, ISBN 0-521-01012-8.
• Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage, Vieweg-Teubner, Wiesbaden 2009, ISBN 978-3-8348-0629-1.
• Hubertus Th. Jongen: Optimierung B. Skript zur Vorlesung, Verlag der Augustinus-Buchhandlung, Aachen, ISBN 3-925038-19-1
• P. Läuchli: Matroide, Eine Einführung für Mathematiker und Informatiker. Hochschulverlag vdf, Zürich 1998, ISBN 3-7281-2470-2

Weblinks

Mark Hubenthal: A Brief Look At Matroids (pdf) (enthält viele Beweise der hier gemachten Aussagen über Matroide)

Alexander Hölzle: Einführung in die Theorie der Matroide (pdf) (Beispiele und Beweise der wichtigsten Sätze)