\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\)

Schon vor 2 Jahren hatte ich einen Artikel
'Was ist ein Matroid' geschrieben, der mir
heute aber nicht mehr gefiel.
Hier ist eine überarbeitet und erweiterte Fassung. Ich werde erklären, was ein Matroid ist, warum
man sich damit beschäftigt und der Frage
nachgehen, in welchem Sinne Matroide nützlich sind. define(M, \big\M) define(E, \big\E) define(I, \big\I) Definition__: Ein Matroid \M=(\E\,\I) ist eine mathematische Struktur, in der \E eine endliche Menge ist und \I eine Familie von Teilmengen von \E, so daß gilt: \ll(M1)\0\el\I, und jede Teilmenge einer zu \I gehörenden Menge gehört ebenfalls zu \I. \ll(M2)(Austauschaxiom) Sind I_p und I_(p+1) Mengen aus \I mit p bzw. p\+1 Elementen, dann gibt es ein Element x\el\ I_(p+1)|\\ I_p\., so daß I_p\union\menge(x)\el\I. Die Elemente von \I nennt man unabhängige__ Mengen von \M. Eine Teilmenge von \E, die nicht in \I ist, heißt abhängig__. Eine mengentheoretisch maximale, unabhängige Menge in \I ist eine Basis__. Eine mengentheoretisch minimale, abhängige Menge ist ein Kreis__. \big\Beispiel: graphische Matroide Sei nun \G=(K,E) ein Graph. K die Menge der Ecken (engl. knots) und E die Menge der Kanten (edges). Die Menge der Kanten ist in einem Graphen eine Menge von Paaren von Elementen aus K. Man nennt E die Inzidenzrelation auf K, weil E angibt, welche Ecken aus K (durch eine Kante) zueinander in Beziehung stehen (miteinander verbunden sind = inzident sind). Wenn wir für einen Graphen \G die Menge \I als Menge der Teilmengen von E definieren, die keine Kreise enthalten, dann ist \M(\G)=(\E,\I) ein Matroid. Die Menge \I erfüllt Axiom \ref(M1), denn jede Teilmenge von \I enthält ebenfalls keinen Kreis in \G, gehört also auch zu \I. Insbesondere enthält die leere Kantenmenge keine Kreise.

Matroide? Ein Fazit

Leider sehe ich im Moment keinen Weg, wie man einerseits schnell auf einen Punkt kommt und andererseits Matroide wirklich benötigt. Mindestens fast alle praktischen algorithmischen Probleme sind in einer Formulierung für Graphen oder Vektorräume weit griffiger und - soweit befriedigend gelöst - auch angemessen dargestellt und gelöst.

Darüber hinaus gibt es sehr wohl Probleme, die zwar mit Matroiden, aber weder durch Graphen noch Vektorräume beschrieben werden können. Allerdings gibt es auch dafür konkretere Theorien. Man kann Zuordnungs- und Partitionierungsprobleme auch jeweils im originären Kontext betrachten und hat das längst getan. Man kann z.B. Tennisturniere oder magische Quadrate mit Hilfe von 'Block-Designs' und 'Galois-Ebenen' beschreiben und deren Lösbarkeit und Lösungsvielfalt bestimmen.
Allerdings sind Galois-Ebenen auch Matroide.

In meiner lange zurückliegenden Diplom-Arbeit habe ich mich mit 'Flußproblemen in Matroiden' beschäftigt. Matroide gestatten eine Beschreibung solcher Probleme und die Charakterisierung der Lösbarkeit.
Zum damaligen Zeitpunkt lieferte die Matroid-Theorie aber keine neuen Verfahren, mit denen praktische Probleme besser als vorher zu behandeln gewesen wären.
Ergebnisse der Theorie waren Charakterisierungssätze wie:

"Ein bestimmtes Flußproblem in einem Matroid ist lösbar, wenn der Matroid keinen zur Fano-Ebene isomorphen Untermatroid ('Minor') enthält.

Die Fano-Ebene hat 7 Punkte und je 3 Punkte auf einer Geraden. Mit der Menge der Kreise definiert als die Punktmengen, die entweder genau alle Punkte einer Geraden enthalten, oder genau das Komplement einer Geraden sind, bildet F₇ einen Matroid. Die Abbildung am Anfang zeigt, wie man sich eine Fano-Ebene veranschaulicht.

Mein Fazit: Matroide sind theoretisch hochinteressant, weil sie so vieles vereinen, sie vereinfachen aber nichts.

Ich lasse mich aber gern eines besseren belehren.

Matroid 2003