Ein Matroid (n.) ist eine mathematische Struktur, mit deren Hilfe der Begriff der Unabhängigkeit aus der linearen Algebra verallgemeinert wird. Es stellt einen Spezialfall der allgemeineren Unabhängigkeitssysteme dar. Matroide besitzen Anwendungen in vielen Bereichen der Kombinatorik, insbesondere der kombinatorischen Optimierung, sowie der Graphentheorie.
Terminologie Hassler Whitney gebrauchte 1935 in seinem grundlegenden Artikel den Begriff Matroid.Hassler Whitney: On the abstract properties of linear dependence. In: Amer. J. Math. 57, 3, 1935, S. 509–533. Wie das Wort andeutet, konzipierte er ein Matroid als abstrakte Verallgemeinerung einer Matrix, wobei das aus dem Griechischen stammende Suffix -oid den Begriff vervollständigt. Ein großer Teil der Sprache dieser Theorie basiert auf der linearen Algebra. Allerdings beruht Whitneys Ansatz auch auf seinen Arbeiten in der Graphentheorie, wodurch die Matroid-Terminologie auch graphentheoretisch geprägt ist. Die Terminologie variiert jedoch von Autor zu Autor. Sogar der Ausdruck Matroid wird von einigen abgelehnt. Leonid Mirsky und Hazel Perfect gebrauchen den Ausdruck „independence space“Leonid Mirsky, Hazel Perfect: Applications of the notion of independence to combinatorial analysis. In: J. Combinatorial Theory. 2, 1967, S. 317–357. (dt. i. e. Unabhängigkeits-Raum), Henry H. Crapo und Gian-Carlo Rota in ihrer Monographie zur kombinatorischen Geometrie „pregeometry“Henry H. Crapo, Gian-Carlo Rota: On the Foundations of Combinatorial Theory: Combinatorial Geometries. Cambridge, MIT Press 1970. (dt. Prägeometrie), Richard Rado „independence functions“ (dt. i. e. Unabhängigkeits-Funktionen) und Paul Cohn „transitive dependence relation“Paul M. Cohn: Universal Algebra. Harper & Row, 1965. (dt. i. e. transitive Abhängigkeits-Relation). Nach Martin Aigner betont der Begriff Matroid den mengentheoretischen Standpunkt etwas stärker, während Prägeometrie vor allem von jenen Autoren verwendet wird, die den geometrischen Aspekt in den Vordergrund rücken.Martin Aigner: Kombinatorik II. S. 15–16.
Historische Betrachtung mini|hochkant|Der Mathematiker Hassler Whitney, der den Begriff Matroid einführte
Matroide wurden in den 1930er-Jahren von mehreren Autoren eingeführt und weiterentwickelt. Es ging darum, bekannte Konzepte und Begrifflichkeiten der linearen Algebra – wie etwa lineare Abhängigkeit und Unabhängigkeit, Basis und Erzeugnis – zu axiomatisieren und auf allgemeinere Strukturklassen zu übertragen. Dadurch wurde die Präzisierung gewisser Begriffsbildungen in verschiedenen Gebieten der Kombinatorik ermöglicht und rein kombinatorische Fragen wurden algebraischen Ideen und Methoden zugänglich gemacht. Nicht zuletzt haben sich auf diesem Wege viele Betrachtungen der Graphentheorie in die Theorie der Matroide einordnen lassen.
In der Regel wird der Beginn der Matroid-Theorie dem US-amerikanischen Mathematiker Hassler Whitney zugerechnet. Dieser untersuchte 1935 matrische Matroide , bei denen die Elemente von die Zeilen einer gegebenen Matrix sind, und eine Menge von Zeilen unabhängig ist, wenn die Zeilen im gewöhnlichen Sinn linear unabhängig sind. Etwas später benutzte auch Bartel Leendert van der Waerden in seinem Buch „Moderne Algebra“ das Konzept einer abstrakten Abhängigkeit.Bartel Leendert van der Waerden: Moderne Algebra. 2. Auflage. Springer, Berlin 1937. Unabhängig davon verfasste der japanische Mathematiker Takeo Nakasawa zwischen 1935 und 1938 vier Artikel, die ihn zum Mitbegründer der Matroid-Theorie machen, wenn auch diese für lange Zeit in Vergessenheit gerieten.Hirokazu Nishimura, Susumu Kuroda (Hrsg.): A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory. Birkhäuser, Basel / Boston / Berlin 2009.
Daneben erschienen vereinzelte Artikel von Garrett Birkhoff (1935),Garrett Birkhoff: Abstract linear dependence in lattices. In: Amer. J. Math. 57, 1935, S. 800–801. Saunders Mac Lane (1936)Saunders MacLane: Some interpretations of abstract linear dependence in terms of projective geometry. In: Amer. J. Math. 58, 1936, 236–240. und Robert P. Dilworth (1941–1944)Robert P. Dilworth: Ideals in Birkhoff lattices. In: Trans. Amer. Math. Soc. 49, 1941, S. 325–353; Arithmetic theory of Birkhoff lattices. In: Duke Math. J. 8, 1941, S. 286–299; Dependence relations in a semimodular lattice. In: Duke Math. J. 11, S. 575–587. zu verbandstheoretischen und geometrischen Aspekten der Matroid-Theorie. Richard Rado beschäftigte sich mit kombinatorischen Anwendungen von Matroiden (1942)Richard Rado: A theorem on independence relations. In: Quart. J. Math. 13, 1942, S. 83–89. und unendlichen Matroiden (1949).Richard Rado: Axiomatic treatment of rank in infinite sets. In: Canad. J. Math. 1, 1949, S. 337–343. Wichtiger Anstoß für die weitere Entwicklung der Theorie der Matroide war die wechselweise Übernahme von Ideen aus verschiedenen Gebieten und ihre Auswirkungen in anderen, wie beispielsweise die Parallelität zwischen den Eigenschaften der Dimension in Vektorräumen und des Ranges in Graphen. 1958 und 1959 veröffentlichte William Thomas Tutte grundlegende Artikel zu Matroiden und Graphen.William Thomas Tutte: A homotropy theory for matroids, I and II. In: Trans. Amer. Math. Soc. 88, 1958, S. 144–174; Matroids and graphs. In: Trans. Amer. Math. Soc. 90, 1959, S. 527–552. Seither nahm das Interesse an Matroiden und ihren Anwendungen in der Kombinatorik stetig zu, nicht zuletzt im Bereich der kombinatorischen Optimierung.Welsh: Matroids. In: Handbook of Combinatorics. S. 483. Jack Edmonds und Delbert Ray Fulkerson (1965)Jack Edmonds, Delbert R. Fulkerson: Transversals and matroid partition. In: J. Res. Nat. Bar. Stand. 69B, 1965, S. 147–153. sowie Leonid Mirsky und Hazel Perfect (1967) entdeckten unabhängig voneinander eine neue Klasse von Matroiden, sogenannte transversale Matroide. Nach Welsh erzielten Matroide bisher in der Transversaltheorie den größten Effekt (gemessen an neuen Resultaten, die dadurch erreicht wurden und einfacheren Beweisen, die für bereits bekannte Resultate gefunden wurden).D. J. A. Welsh: Matroid Theory. 1976, S. 6.
Einführende Beispiele Beispiel für einen Vektormatroiden mini|Gegeben ist die Grundmenge E mit den Vektoren a, b, c, d, e, f. Die Mengen mit dem Nullvektor f und die Mengen, die die Vektoren d und e gemeinsam enthalten, sind linear abhängig.
Sei ein Körper, ein -Vektorraum und eine endliche Teilmenge. Sei als die Menge der Teilmengen von definiert, die in linear unabhängig über sind. Dann ist das Paar ein Matroid, genannt Vektormatroid.
Seien beispielsweise der -Vektorraum und als Grundmenge die Spalten der folgenden Matrix gegeben:Die einführenden Beispiele orientieren sich an Beispielen aus einer Einführungsvorlesung zum Thema Matroid, die 2007 von Frederico Ardila an der San Francisco State University gehalten wurde. Siehe dazu dieses Video und diese Vorlesungsnotizen.
Die entsprechenden Spaltenvektoren werden wie folgt bezeichnet:
Daraus ergibt sich die Grundmenge und die Menge
der Vektormengen mit jeweils zueinander linear unabhängigen Vektoren.
Demgegenüber sind die Vektoren im Vektorraum linear abhängig, wenn eine der folgenden Bedingungen erfüllt ist: Es handelt sich um eine einelementige Menge, die genau den Nullvektor enthält. Im obigen Beispiel wäre dies der Vektor . Zwei oder mehrere Vektoren sind skalare Vielfache voneinander. Im Beispiel sind dies Mengen mit den Vektoren und und alle Mengen, die den Vektor enthalten.
Entsprechend sind eine Nullspalte und skalare Vielfache bzw. dessen Indizes in einem Matroid abhängig.
Für ein Matroid sind die Basen als die inklusionsmaximalen Elemente von definiert. Für ein Vektormatroid sind dies genau die Basen des Vektorraumes. Im vorliegenden Beispiel gilt somit:
.
Beispiel für ein graphisches Matroid Sei ein ungerichteter Multigraph (d. h. Mehrfachkanten und Schleifen sind möglich) mit Knotenmenge und Kantenmenge . Das graphische Matroid enthält als unabhängige Mengen gerade die kreisfreien Teilgraphen von .
Als Beispiel sei der Graph mit der Knotenmenge und der Kantenmenge gegeben, wobei die Kanten durch folgende Multimengen definiert seien: .
500px|Graph G = (V,E) mit der Kantenmenge E = {a, b, c, d, e, f}
In diesem Beispiel entsprechen die kreisfreien Teilgraphen unabhängigen Mengen .
Die Basen eines graphischen Matroids entsprechen den Spannwäldern des Graphen (bzw. den Spannbäumen bei zusammenhängenden Graphen). Für das Beispiel gilt somit:
.
Axiomatisierung In der Matroidtheorie gibt es kein Standardaxiomensystem. Bereits Whitney bemerkte im grundlegenden Artikel, dass sich verschiedene Strukturen in den Matroiden zur Axiomatisierung anbieten. Da die eine Struktur jeweils die andere impliziert, kann ein Matroid somit auf viele verschiedene äquivalente Weisen definiert werden. So sind die Unabhängigkeitsaxiome eher durch die lineare Algebra motiviert, während die Kreisaxiome sich eher an einem graphentheoretischen Zugang orientieren. Birkhoff führte für eine solche Äquivalenz verschiedener Axiomatisierungen den Begriff Kryptomorphismus ein. Damit soll gesagt werden, dass zwei Axiomatisierungen auf nicht offensichtliche oder gar kryptische Weise „isomorph“ sind.
Unabhängigkeitsaxiome Ein Matroid ist ein geordnetes Paar bestehend aus einer endlichen Menge , Grundmenge genannt, und einer Menge von Teilmengen (Mengensystem), unabhängige Mengen genannt, das folgende Axiome erfüllt:Die Notation der grundlegenden Definitionen orientiert sich an Oxley: Matroid Theory. S. 7–15.
(I1) .
(I2) Wenn und , dann ist .
(I3) Wenn und in sind und , dann gibt es ein Element aus , so dass
Dabei ist die Kardinalität der Menge und meint die Differenz der Mengen und . Oft schreibt man auch für und für , insbesondere wenn mehrere Matroide berücksichtigt werden. Die Mengen aus werden abhängig genannt.
Das erste Axiom besagt, dass die leere Menge unabhängig ist. Entsprechend dem zweiten Axiom ist jede Teilmenge einer unabhängigen Menge ebenfalls unabhängig. Man sagt diesbezüglich auch, dass das Mengensystem erblich oder hereditär ist. Das Alleinstellungsmerkmal eines Matroides gegenüber einem gewöhnlichen Unabhängigkeitssystem besteht in der Austauscheigenschaft, also der dritten Bedingung. Während sich die ersten beiden Axiome leicht als Forderungen der Existenz mindestens einer unabhängigen Menge und der Abgeschlossenheit des Systems bezüglich der Inklusion verstehen lassen, so ist die Motivation der Austauscheigenschaft weniger offensichtlich.
Man kann sich diese wie folgt veranschaulichen: Durch Anwendung der Austauscheigenschaft lassen sich Punkte einer unabhängigen Menge zu einer (kleineren) unabhängigen Menge hinzufügen. Deshalb spricht man auch von der Vergrößerungseigenschaft (von engl. augmentation property). Von der so erzeugten Menge weiß man, dass sie ebenfalls wieder unabhängig ist. Sie enthält nun zwar Elemente der Menge , allerdings wurden im Vergleich zu dieser die übrigen enthaltenen Punkte durch Elemente aus ersetzt. Dies begründet wiederum den Namen Austauscheigenschaft.G. Meyer: Vorlesung: Algorithmen und Datenstrukturen 2; Universität Leipzig; Wintersemester 2000; C. Kingsford: CMSC 451: Matroids, When Greed Works (PDF; 93 kB); Lecture Slides; Departement of Computer Science, University of Maryland; 2009; College Park, US-MD.
Basisaxiome Eine Basis ist ein bezüglich der Mengeninklusion maximales Element des Mengensystems . Durch eine Menge aller maximal unabhängigen Mengen lässt sich ein Matroid effizienter spezifizieren als durch die Aufführung aller unabhängigen Mengen.
Für eine Grundmenge und eine Menge der Basen ist das geordnete Paar ein Matroid, wenn die folgenden Axiome erfüllt sind:Für einen Beweis der Kryptomorphie zwischen Unabhängigkeitsaxiomen und Basisaxiomen siehe z. B. Oxley: Matroid Theory. S. 16–18.
(B1) (B2) Für Basen und von und jedes gibt es ein , sodass .