Matroide
Eine Einführung für Informatiker und Mathematiker
Peter Läuchli
„Wer noch nichts über Matroide weiss, möge das eher leichtfüssig daherkommende Einleitungskapitel lesen. Sie oder er wird darin bereits die Idee der Matroide erkennen. Anhand eines sehr einfachen Beispiels erkläre ich die in den späteren Kapiteln verfolgten vier Hauptrichtungen. Das obligate Kapitel 1 über mathematische Präliminarien ist etwas ausführlich geraten. Es soll die nicht überall gleich gehandhabte Terminologie fixieren und einige vielleicht nicht so geläufige Grundlagen für den Umgang mit Mengenfamilien bereitstellen. In Kapitel 2 werden die Elemente der Matroidtheorie, insbesondere auch das Konzept der Dualität und dasjenige der kryptomorphen Axiomatisierungen eingeführt. Als Illustration dient hier vor allem die lineare Algebra. Kapitel 3 bringt die Verbindungen zur Graphentheorie, mit spezieller Berücksichtigung der Planariät. Auch der wichtige Begriff des Minors kommt zur Sprache. In Kapitel 4 werden die Matroide als kombinatorische Geometrien in den Zusammenhang mit den Inzidenzstrukturen und der Theorie der Verbände gestellt. Der kombinatorische Begriff der Transversalen wird in Kapitel 5 als ein weiterer Zugang zu den Matroiden erkannt. Schliesslich folgt in Kapitel 6 noch ein kurzer Blick auf den Themenkreis der kombinatorischen Optimierung.“
