Matroid

Grundidee und Unabhängigkeitsaxiome

Ein Matroid ist eine mathematische Struktur, die den Begriff der Unabhängigkeit aus der linearen Algebra verallgemeinert. Es ist ein Spezialfall der allgemeineren Unabhängigkeitssysteme und wird unter anderem in der Kombinatorik, der kombinatorischen Optimierung und der Graphentheorie verwendet.

Ein Matroid M = (E, 𝓘) besteht aus einer endlichen Grundmenge E und einem Mengensystem 𝓘 ⊆ P(E) seiner unabhängigen Mengen. Die abhängigen Mengen sind P(E) − 𝓘. Das Mengensystem muss folgende Unabhängigkeitsaxiome erfüllen:

• (I1) ∅ ∈ 𝓘: Die leere Menge ist unabhängig.
• (I2) Ist I ∈ 𝓘 und I′ ⊆ I, dann gilt I′ ∈ 𝓘. Das System ist also erblich oder hereditär.
• (I3) Sind I₁, I₂ ∈ 𝓘 und |I₁| < |I₂|, dann gibt es ein Element e ∈ I₂ − I₁ mit I₁ ∪ {e} ∈ 𝓘. Dies ist die Austausch- oder Vergrößerungseigenschaft.

Das dritte Axiom unterscheidet Matroide von gewöhnlichen Unabhängigkeitssystemen. Es besagt, dass sich eine kleinere unabhängige Menge durch ein geeignetes Element einer größeren unabhängigen Menge erweitern lässt. Für mehrere betrachtete Matroide werden häufig 𝓘(M) und E(M) geschrieben.

Vektormatroid und graphisches Matroid

Beim Vektormatroiden wird lineare Unabhängigkeit unmittelbar als Unabhängigkeit verwendet. Sei L ein Körper, V ein L-Vektorraum und E ⊆ V eine endliche Teilmenge. Definiert man 𝓘 als die Menge aller Teilmengen von E, die in V über L linear unabhängig sind, so ist M = (E, 𝓘) ein Vektormatroid.

Im Beispiel ist V = ℝ³ und E besteht aus den Spalten der Matrix

A = [[1,0,0,0,0,0], [0,1,0,1/2,1,0], [0,0,1,1/2,1,0]].

Die Spalten heißen a = (1,0,0), b = (0,1,0), c = (0,0,1), d = (0,1/2,1/2), e = (0,1,1) und f = (0,0,0). Der Nullvektor f ist abhängig. Ebenso sind d und e sowie jede Menge, die f enthält, abhängig; d und e sind skalare Vielfache voneinander. Die Basen, also die inklusionsmaximalen unabhängigen Mengen, sind

𝓑 = {{a,b,c}, {a,b,d}, {a,b,e}, {a,c,d}, {a,c,e}}.

Ein graphisches Matroid entsteht aus einem ungerichteten Multigraphen G = (V,E), bei dem Mehrfachkanten und Schleifen möglich sind. Seine unabhängigen Mengen sind genau die kreisfreien Teilgraphen. Im Beispiel gilt V = {1,2,3,4}, E = {a,b,c,d,e,f} mit a = {1,2}, b = {2,3}, c = {2,4}, d = {3,4}, e = {3,4} und f = {1,1}. Die Kante f ist eine Schleife und daher abhängig; d und e sind parallele Mehrfachkanten und können nicht gemeinsam in einer kreisfreien Menge liegen.

Die Basen eines graphischen Matroids sind die Spannwälder, bei zusammenhängenden Graphen also die Spannbäume. Für das Beispiel lautet die Basenmenge ebenfalls 𝓑 = {{a,b,c}, {a,b,d}, {a,b,e}, {a,c,d}, {a,c,e}}.

Basen, Kreise und alternative Axiome

Eine Basis ist ein bezüglich der Inklusion ⊆ maximales Element von 𝓘. Sind die Basen 𝓑 gegeben, erhält man die unabhängigen Mengen als alle Teilmengen von Basen. Die Basisaxiome lauten:

• (B1) 𝓑 ≠ ∅.
• (B2) Für B₁, B₂ ∈ 𝓑 und jedes x ∈ B₁ − B₂ gibt es ein y ∈ B₂ − B₁, sodass (B₁ − {x}) ∪ {y} ∈ 𝓑. Dies heißt verallgemeinerter Austauschsatz von Steinitz.

Alle Basen eines Matroids haben dieselbe Kardinalität. Diese gemeinsame Größe ist der Rang des Matroids.

Ein Kreis ist eine inklusionsminimale abhängige Teilmenge. Er ist selbst abhängig, aber jede echte Teilmenge ist unabhängig. Die Kreise 𝓒 werden durch folgende Kreisaxiome charakterisiert:

• (C1) ∅ ∉ 𝓒.
• (C2) Für C₁, C₂ ∈ 𝓒 und C₁ ⊆ C₂ gilt C₁ = C₂.
• (C3) Für verschiedene C₁, C₂ ∈ 𝓒 und e ∈ C₁ ∩ C₂ gibt es einen Kreis C₃ mit C₃ ⊆ (C₁ ∪ C₂) − {e}. Dieses schwache Kreiseliminationsaxiom beschreibt das Entfernen eines gemeinsamen Elements.

Es gibt kein Standardaxiomensystem für Matroide. Unabhängigkeits-, Basis- und Kreisaxiome sowie Rang- und Hüllenaxiome sind äquivalente Beschreibungen. Birkhoff bezeichnete diese nicht offensichtliche Äquivalenz verschiedener Axiomatisierungen als Kryptomorphismus.

Rangfunktion und Hüllenoperator

Für X ⊆ E ist die Restriktion M|X das Matroid auf X mit 𝓘|X = {I ⊆ X : I ∈ 𝓘}. Sie entsteht auch dadurch, dass E − X aus M gelöscht wird. Die Rangfunktion r: P(E) → ℕ₀ ist definiert durch r(X) = |Bₓ| für eine Basis Bₓ der Restriktion M|X. Der Rang misst damit eine Art Dimension: Er ist die Größe einer maximal unabhängigen Teilmenge von X.

Die Rangaxiome sind:

• (R1) 0 ≤ r(X) ≤ |X|.
• (R2) Aus X ⊆ Y ⊆ E folgt r(X) ≤ r(Y).
• (R3) Für X,Y ⊆ E gilt r(X ∪ Y) + r(X ∩ Y) ≤ r(X) + r(Y).

Die Rangfunktion ist somit nicht-negativ und subkardinal, monoton sowie submodular. Eine Menge X ist genau dann unabhängig, wenn |X| = r(X). Sie ist genau dann eine Basis, wenn |X| = r(X) = r(M). Ein nichtleeres X ist genau dann ein Kreis, wenn für alle x ∈ X gilt: r(X − {x}) = |X| − 1 = r(X).

Der Hüllen- oder Abschlussoperator cl: P(E) → P(E) enthält alle Elemente, deren Hinzufügen den Rang nicht erhöht: cl(X) = {x ∈ E : r(X ∪ {x}) = r(X)}. Er erfüllt:

• (CL1) X ⊆ cl(X).
• (CL2) X ⊆ Y ⊆ E impliziert cl(X) ⊆ cl(Y).
• (CL3) cl(cl(X)) = cl(X).
• (CL4) Aus y ∈ cl(X ∪ {x}) − cl(X) folgt x ∈ cl(X ∪ {y}).

Die Basen sind genau die bezüglich der Inklusion minimalen Mengen B mit cl(B) = E.

Greedy-Algorithmen und Hyperebenen

Ein gewichtetes Matroid besitzt zusätzlich eine Gewichtsfunktion w: E → ℝ⁺. Greedy-Algorithmen, die Elemente schrittweise nach Gewichten auswählen und dabei die Unabhängigkeit erhalten, berechnen für solche Matroide stets Basen mit minimalem beziehungsweise maximalem Gesamtgewicht. Ein wichtiges Beispiel ist der Algorithmus von Kruskal zur Berechnung eines minimalen aufspannenden Waldes eines kantengewichteten Graphen. Umgekehrt ist ein Unabhängigkeitssystem genau dann ein Matroid, wenn ein Greedy-Algorithmus für jede Gewichtsfunktion immer Basen minimalen beziehungsweise maximalen Gewichts bestimmen kann.

Eine Hyperebene eines Matroids M auf E ist eine bezüglich des Hüllenoperators s abgeschlossene echte Teilmenge, die bezüglich dieser Eigenschaft maximal ist. Sie erfüllt

• s(H) = H ⊊ E;
• für jedes x ∈ E − H gilt s(H ∪ {x}) = E.

Hat das Matroid endlichen Rang und besitzen alle Basen die Kardinalität ρ, dann ist eine Hyperebene genau eine maximale echte Teilmenge H mit r(H) = ρ − 1. Deshalb wird sie auch Copunkt genannt. Die Hyperebenen bestimmen die Matroidstruktur eindeutig. Durch Komplementbildung stehen sie in einer umkehrbar eindeutigen Beziehung zu den Kreisen des dualen Matroids M*.

Ein Hyperebenensystem 𝓗 ⊆ P(E) ist genau dann das Hyperebenensystem eines Matroids, wenn gilt:

• (H1) E ∉ 𝓗.
• (H2) Für verschiedene H₁,H₂ ∈ 𝓗 gilt H₁ ⊄ H₂; die Hyperebenen bilden also eine Antikette.
• (H3) Für H₁,H₂ ∈ 𝓗 und x ∈ E − (H₁ ∪ H₂) gibt es H₃ ∈ 𝓗 mit H₃ ⊇ (H₁ ∩ H₂) ∪ {x}.

Entstehung und Entwicklung

Die Matroidtheorie entstand in den 1930er-Jahren aus dem Versuch, Begriffe der linearen Algebra wie lineare Abhängigkeit, Unabhängigkeit, Basis und Erzeugnis zu axiomatisieren und auf allgemeinere Strukturen zu übertragen. Dadurch wurden kombinatorische Fragen algebraischen Methoden zugänglich, und viele graphentheoretische Betrachtungen konnten in die Matroidtheorie eingeordnet werden.

Üblicherweise wird der Beginn der Theorie Hassler Whitney zugerechnet. Er untersuchte 1935 matrische Matroide M = (S, 𝓘), bei denen die Elemente von S die Zeilen einer Matrix sind und eine Zeilenmenge genau dann unabhängig ist, wenn sie im gewöhnlichen Sinn linear unabhängig ist. Bartel Leendert van der Waerden verwendete später das Konzept einer abstrakten Abhängigkeit. Unabhängig davon verfasste Takeo Nakasawa zwischen 1935 und 1938 vier einschlägige Artikel.

Weitere Beiträge kamen unter anderem von Garrett Birkhoff (1935), Saunders Mac Lane (1936), Robert P. Dilworth (1941–1944) und Richard Rado (1942 sowie 1949 zu unendlichen Matroiden). William Thomas Tutte veröffentlichte 1958 und 1959 grundlegende Arbeiten zu Matroiden und Graphen. 1965 beziehungsweise 1967 wurden von Jack Edmonds und Delbert Ray Fulkerson sowie unabhängig von Leonid Mirsky und Hazel Perfect die transversalen Matroide entdeckt. Danach wuchs das Interesse besonders wegen der Anwendungen in der kombinatorischen Optimierung stetig.