Matroid

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Matroid (n.) ist eine mathematische Struktur, mit deren Hilfe der Begriff der Unabhängigkeit aus der linearen Algebra verallgemeinert wird. Matroide besitzen Anwendungen in vielen Bereichen der Kombinatorik, insbesondere der kombinatorischen Optimierung, sowie der Graphentheorie.

Terminologie[Bearbeiten | Quelltext bearbeiten]

Hassler Whitney gebrauchte 1935 in seinem grundlegenden Artikel den Begriff Matroid.[1] Wie das Wort andeutet, konzipierte er ein Matroid als abstrakte Verallgemeinerung einer Matrix. Die Endung -oid zu griechisch oides (= ähnlich) vervollständigt den Begriff. 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. Wie so oft in jüngeren Forschungsgebieten variiert jedoch die Terminologie von Autor zu Autor. Sogar der Ausdruck Matroid wird von einigen abgelehnt. Leonid Mirsky und Hazel Perfect gebrauchen den Ausdruck „independence space“[2] (dt. i.e. Unabhängigkeits-Raum), Henry H. Crapo und Gian-Carlo Rota in ihrer Monographie zur kombinatorischen Geometrie „pregeometry“[3] (dt. Prägeometrie), Richard Rado „independence functions“ (dt. i.e. Unabhängigkeits-Funktionen) und Paul Cohn „transitive dependence relation“[4] (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.[5]

Historische Betrachtung[Bearbeiten | Quelltext bearbeiten]

Der Mathematiker Hassler Whitney, der den Begriff Matroid einführte

Die mathematische Struktur eines Matroids wurde in den 1930er-Jahren von mehreren Autoren eingeführt und weiterentwickelt. Es ging darum, bekannte Begriffe aus der linearen Algebra wie lineare Abhängigkeit, Basis und Erzeugnis zu axiomatisieren und auf allgemeinere Strukturklassen zu übertragen. Dies ermöglicht eine präzisere Begriffsbildung in verschiedenen Gebieten der Kombinatorik und macht rein kombinatorische Fragen algebraischen Ideen und Methoden zugänglich. So lässt sich beispielsweise die Graphentheorie in die Theorie der Matroide einreihen.

In der Regel wird der Beginn der Matroid-Theorie dem US-amerikanischen Mathematiker Hassler Whitney zugerechnet. Dieser untersuchte 1935 matrische Matroide M=(S,I), bei denen die Elemente von S 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.[6] Etwas später benutzte auch Bartel Leendert van der Waerden in seinem Buch „Moderne Algebra“ das Konzept einer abstrakten Abhängigkeit.[7] 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.[8]

Daneben erschienen vereinzelte Artikel von Garrett Birkhoff (1935)[9], Saunders MacLane (1936)[10] und Robert P. Dilworth (1941–1944)[11] zu verbandstheoretischen und geometrischen Aspekten der Matroid-Theorie. Richard Rado beschäftigte sich mit kombinatorischen Anwendungen von Matroiden (1942) [12] und unendlichen Matroiden (1949)[13]. 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[14]. Seither nahm das Interesse an Matroiden und ihren Anwendungen in der Kombinatorik stetig zu, nicht zuletzt im Bereich der kombinatorischen Optimierung.[15] Jack Edmonds und Delbert Ray Fulkerson (1965)[16] sowie Leonid Mirsky und Hazel Perfect (1967)[2] 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).[17]

Einführende Beispiele[Bearbeiten | Quelltext bearbeiten]

Beispiel für ein Vektormatroid[Bearbeiten | Quelltext bearbeiten]

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 L ein Körper, V ein L-Vektorraum und E \subseteq V eine endliche Teilmenge. Sei \mathcal I als die Menge der Teilmengen von E definiert, die in V linear unabhängig über L sind. Dann ist das Paar M = (E, \mathcal I ) ein Matroid, genannt Vektormatroid.

Seien beispielsweise der \R-Vektorraum V = \R^3 und als Grundmenge E die Spalten der folgenden Matrix gegeben [18]:


  A :=
  \begin{pmatrix}
    1 & 0 & 0 & 0 & 0 & 0 \\
    0 & 1 & 0 & 0.5 & 1 & 0 \\
    0 & 0 & 1 & 0.5 & 1 & 0
  \end{pmatrix}

Die entsprechenden Spaltenvektoren werden wie folgt bezeichnet:

a := \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, b := \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, c := \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}, d := \begin{pmatrix} 0 \\ 0.5 \\ 0.5 \end{pmatrix}, e := \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}, f := \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}

Daraus ergibt sich die Grundmenge E = \{ a, b, c, d, e, f \} und die Menge

\mathcal I = \{ \emptyset, \{a \}, \{b \}, \{c \}, \{d \}, \{e \}, \{a, b \}, \{a, c \}, \{a, d \}, \{a, e \}, \{b, c \}, \{b, d \}, \{b, e \}, \{c, d \}, \{c, e \},
\{a, b, c \}, \{a, b, d \}, \{a, b, e \}, \{a, c, d \}, \{a, c, e \} \} \subseteq \mathcal P(E)

der Vektormengen mit jeweils zueinander linear unabhängigen Vektoren.

Demgegenüber sind die Vektoren im Vektorraum V 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 f.
  • Zwei oder mehrere Vektoren sind skalare Vielfache voneinander. Im Beispiel sind dies Mengen mit den Vektoren d und e und alle Mengen, die den Vektor f enthalten.

Entsprechend sind eine Nullspalte und skalare Vielfache bzw. dessen Indizes in einem Matroid abhängig.

Für ein Matroid sind die Basen \mathcal B als die inklusionsmaximalen Elemente von \mathcal I definiert. Für ein Vektormatroid M = (V, \mathcal I ) sind dies genau die Basen des Vektorraumes. Im vorliegenden Beispiel gilt somit:

\mathcal B = \{ \{a, b, c \}, \{a, b, d \}, \{a, b, e \}, \{a, c, d \}, \{a, c, e \} \}.

Beispiel für ein graphisches Matroid[Bearbeiten | Quelltext bearbeiten]

Sei G = (V,E) ein ungerichteter Multigraph (d. h. Mehrfachkanten und Schleifen sind möglich) mit Knotenmenge V und Kantenmenge E. Das graphische Matroid  M = (E, \mathcal I) enthält als unabhängige Mengen gerade die kreisfreien Teilgraphen von G.

Als Beispiel sei der Graph G = (V,E) mit der Knotenmenge V = \{ 1, 2, 3, 4 \} und der Kantenmenge E = \{a, b, c, d, e, f \} gegeben, wobei die Kanten durch folgende Multimengen definiert seien: a = \{1, 2 \}, b = \{2, 3 \}, c = \{2, 4 \}, d = \{3, 4 \}, e = \{3, 4 \}, f = \{1, 1 \}.[18]

Graph G = (V,E) mit der Kantenmenge E = {a, b, c, d, e, f}

In diesem Beispiel entsprechen die kreisfreien Teilgraphen als unabhängige Mengen \mathcal I = \{ \emptyset, \{a \}, \{b \}, \{c \}, \{d \}, \{e \}, \{a, b \}, \{a, c \}, \{a, d \}, \{a, e \}, \{b, c \}, \{b, d \}, \{b, e \}, \{c, d \}, \{c, e \}, \{a, b, c \}, \{a, b, d \}, \{a, b, e \}, \{a, c, d \}, \{a, c, e \} \} \subseteq \mathcal P(E).

Die Basen \mathcal B eines graphischen Matroids entsprechen den Spannwäldern des Graphen (bzw. den Spannbäumen bei zusammenhängenden Graphen). Für das Beispiel gilt somit:

\mathcal B = \{ \{a, b, c \}, \{a, b, d \}, \{a, b, e \}, \{a, c, d \}, \{a, c, e \} \}.

Axiomatisierung[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Ein Matroid M ist ein geordnetes Paar (E,\mathcal I) bestehend aus einer endlichen Menge E, Grundmenge genannt, und einer Menge \mathcal I \subseteq \mathcal P(E) von Teilmengen (Mengensystem), unabhängige Mengen genannt, das folgende Axiome erfüllt[19]:

(I1) \emptyset \in \mathcal I.
(I2) Wenn I \in \mathcal I und  I' \subseteq I, dann ist I' \in \mathcal I.
(I3) Wenn I_1 und I_2 in \mathcal I sind und \left| I_1 \right| < \left| I_2 \right|, dann gibt es ein Element e aus I_2 - I_1, so dass I_1 \cup e \in \mathcal I.

Dabei ist \left| I_1 \right| die Kardinalität der Menge I_1 und I_2 - I_1 meint die Differenz der Mengen I_2 und I_1. Oft schreibt man auch \mathcal I(M) für \mathcal I und E(M) für E, insbesondere wenn mehrere Matroide berücksichtigt werden. Die Mengen aus \mathcal P(E) - \mathcal I 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 \mathcal I 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 I_2 zu einer (kleineren) unabhängigen Menge I_1 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 I_1, allerdings wurden im Vergleich zu dieser die übrigen enthaltenen Punkte durch Elemente aus I_2 - I_1 ersetzt. Dies begründet wiederum den Namen Austauscheigenschaft.[20]

Basisaxiome[Bearbeiten | Quelltext bearbeiten]

Eine Basis ist ein bezüglich der Mengeniklusion  \subseteq maximales Element des Mengensystems \mathcal I. Durch eine Menge \mathcal B aller maximal unabhängigen Mengen lässt sich ein Matroid M effizienter spezifizieren als durch die Aufführung aller unabhängigen Mengen.

Für eine Grundmenge E und eine Menge \mathcal B \subseteq \mathcal P(E) der Basen ist das geordnete Paar (E, \mathcal B) ein Matroid, wenn die folgenden Axiome erfüllt sind[21]:

(B1) \mathcal B \neq \emptyset
(B2) Für Basen B_1 und B_2 von \mathcal B und jedes x \in B_1 - B_2 gibt es ein y \in B_2 - B_1, sodass (B_1 - x) \cup y \in \mathcal B.

Die Bedingung (B2) wird auch als der verallgemeinerte Austauschsatz von Steinitz bezeichnet. Sind die Basen \mathcal B eines Matroids gegeben, lassen sich die unabhängigen Mengen \mathcal I als Menge aller Teilmengen von Basen aus \mathcal B herleiten.

Zwei Basen eines Matroids besitzen stets dieselbe Kardinalität: Wenn B_1 und B_2 Basen eines Matroids M sind, dann gilt | B_1 | = | B_2 |.

Beweis: Man nehme an, dass | B_1 | < | B_2 |. Da B_1 und B_2 beide unabhängig in M sind, impliziert (I3), dass es ein Element e aus B_2 - B_1 gibt, so dass B_1 \cup e \in \mathcal I. Dies widerspricht der Maximalität von B_1, also | B_1 | \geq |B_2|. Auf gleiche Weise lässt sich | B_2 | \geq |B_1| zeigen und daraus folgt | B_1 | = |B_2|

Kreisaxiome[Bearbeiten | Quelltext bearbeiten]

Axiom C3: In der Vereinigung von C_1 (rot) und C_2 (grün) ist ein Kreis C_3 enthalten, der eine gemeinsame Kante e (rot-grün gestrichelt) nicht enthält.

Eine inklusionsminimale abhängige Teilmenge eines beliebigen Matroids M wird Kreis genannt. Die Menge der Kreise von M wird mit \mathcal C oder \mathcal C(M) bezeichnet. Ein Kreis C \in \mathcal C ist also nicht unabhängig, aber jede echte Teilmenge von C ist unabhängig. Ein Kreis von M mit n Elementen wird auch n-Kreis genannt. Offensichtlich kann \mathcal I(M) aus \mathcal C(M) bestimmt werden und umgekehrt \mathcal C(M) aus \mathcal I(M).

Für eine Grundmenge E und eine Menge \mathcal C \subseteq \mathcal P(E) der Kreise ist das geordnete Paar (E,\mathcal C) ein Matroid M, wenn \mathcal C folgende Axiome erfüllt[22]:

(C1) \emptyset \notin \mathcal C.
(C2) Wenn C_1, C_2 \in \mathcal C und C_1 \subseteq C_2, dann folgt C_1 = C_2.
(C3) Für alle C_1, C_2 \in \mathcal C mit C_1 \neq C_2 und e \in C_1 \cap C_2 gibt es C_3 \in \mathcal C, sodass C_3 \subseteq (C_1 \cup C_2) - \{e \}.

Die minimal abhängigen Teilmengen eines Matroides bilden stets ein Kreissystem. Besonders anschaulich wird dies in graphischen Matroiden, da dort die Elemente von \mathcal C die Kreise des zugrundeliegenden Graphens enthalten, woher auch die Bezeichnung stammt. Die Eigenschaft (C3) wird auch (schwaches) Kreiseliminationsaxiom genannt: Zu je zwei verschiedenen Kreisen C_1 und C_2 und einem Element e aus dem Schnitt dieser beiden Kreise, gibt es einen dritten Kreis C_3, der in den beiden Kreisen C_1 und C_2 enthalten ist und das gewählte Element e aus dem Schnitt vermeidet.[23]

Axiome der Rangfunktion[Bearbeiten | Quelltext bearbeiten]

Sei M = (E, \mathcal I) ein Matroid und X \subseteq E. Sei nun \mathcal I | X definiert als \{ I \subseteq X: I \in \mathcal I \}. Das Paar (X, \mathcal I | X) ist wiederum ein Matroid. Dieses wird Restriktion von M auf X genannt und mit M | X oder M \backslash (E-X) gekennzeichnet. Man sagt auch, dass E-X aus M gelöscht wird.

Für ein Matroid M=(E, \mathcal I) definiert man seine Rangfunktion r: \mathcal P(E) \to \N_0 als

X \mapsto r(X) := |B_X| für ein B_X \in \mathcal B(\mathcal I | X).

Der Rang eines Matroids M ist also die Mächtigkeit einer (und damit jeder) Basis B von M. Er soll eine Art „Dimension“ eines Matroids beschreiben. Der Rang einer Teilmenge X \subseteq E eines Matroids M = (E, \mathcal I) entspricht der Mächtigkeit einer (und damit aller) maximal unabhängiger Elemente der Restriktion von M auf X. Man beachte, dass eine Restriktion M|X stets durch Löschen der Teilmenge T=(E-X) aus der Grundmenge E entsteht.[24]

Mit Hilfe von Rangfunktionen lässt sich nun ein weiteres äquivalentes Axiomensystem für Matroide entwickeln. Es seien M = (E, \mathcal I) ein Matroid und r: \mathcal P(E) \to \N_0 dessen Rangfunktion, dann gilt:

(R1) Wenn X \subseteq E, dann 0 \le r(X) \le |X|.
(R2) Wenn X \subseteq Y \subseteq E, dann r(X) \le r(Y).
(R3) Für alle X,Y \in E gilt: r(X \cup Y) + r(X \cap Y) \le r(X) + r(Y).

Die Rangfunktion r ist somit nicht-negativ und subkardinal (R1), monoton (R2) und submodular (R3). Die letzte Eigenschaft erinnert außerdem an die Dimensionsformel aus der linearen Algebra.

Unabhängige Mengen, Basen und Kreise können relativ einfach durch die Rangfunktion charakterisiert werden. Sei M ein Matroid mit Rangfunktion r und sei X \subseteq E(M). Dann gilt

  • X ist unabhängig genau dann wenn |X| = r(X);
  • X ist eine Basis genau dann wenn |X|=r(X)=r(M); und
  • X ist ein Kreis genau dann wenn X nicht leer ist und für alle x in X gilt r(X-x)=|X|-1=r(X).

Axiome des Hüllenoperators[Bearbeiten | Quelltext bearbeiten]

Die lineare Hülle \langle A \rangle einer Teilmenge A eines Vektorraums V über einem Körper K ist die Menge aller Linearkombinationen mit Vektoren aus A mit Skalaren aus K. Die lineare Hülle bildet einen Untervektorraum, der gleichzeitig der kleinste Untervektorraum ist, der A enthält. Ist z. B. die Menge \{ a_1,...,a_k\} von Vektoren des Vektorraums V gegeben, dann wirken sich sämtliche Vektoren des Untervektorraums \langle a_1,...a_k \rangle invariant gegenüber der Dimension dim(A) aus. Die Dimension wird durch diese Vektoren also nicht vergrößert.[25]

Mit dem Hüllenoperator (auch Abschlussoperator) cl: \mathcal P(E) \to \mathcal P(E) werden nun diejenigen Elemente x \in E eines Matroids M ausgezeichnet, die den Rang gegenüber einer Teilmenge X \subseteq E nach Hinzufügen eines der Elemente nicht verändern:

cl(X) = \{ x \in E : r(X \cup x) = r(X) \}

Der Hüllenoperator eines Matroids M auf einer Grundmenge E hat nun folgende Eigenschaften:

(CL1) Wenn X \subseteq E , dann X \subseteq cl(X).
(CL2) Wenn X \subseteq Y \subseteq E, dann cl(X) \subseteq cl(Y).
(CL3) Wenn X \subseteq E, dann cl(cl(X))=cl(X).
(CL4) Wenn X \subseteq E, x \in E und y \in cl(X \cup x) - cl(X), dann x \in cl(X \cup y).

Greedy-Algorithmen[Bearbeiten | Quelltext bearbeiten]

Ein gewichteter Matroid ist ein Matroid mit einer Gewichtsfunktion w \colon E \to \R^+. Für diese Matroide berechnen Greedy-Algorithmen stets Basen mit minimalem bzw. maximalem Gewicht. Ein Beispiel ist der Algorithmus von Kruskal zur Berechnung eines minimalen aufspannenden Waldes eines kantengewichteten Graphen.

Ein Unabhängigskeitssystem ist umgekehrt genau dann ein Matroid, wenn ein Greedy-Algorithmus zu jeder Gewichtsfunktion immer Basen mit minimalen/maximalen Gewicht berechnen kann.[20]

Matroide und Hyperebenen[Bearbeiten | Quelltext bearbeiten]

Einen wichtigen Zusammenhang zwischen Matroidtheorie und Geometrie und vor allem zwischen Matroiden und endlichen geometrischen Strukturen findet man über den Begriff der Hyperebene. Hierbei bezeichnet man innerhalb eines Matroids M über der Grundmenge E als Hyperebene eine unter dem zugehörigen Hüllenoperator s abgeschlossene echte Teilmenge von E, welche bezüglich dieser Eigenschaft maximal ist.

Eine Hyperebene H von M zeichnet sich also durch zwei Eigenschaften aus:[26]

  1. s(H) = H \subsetneqq E
  2. \forall x \in {E \setminus H} \colon s(H \cup \{ x \}) = E

Bei Matroiden endlichen Ranges, deren Basismengen B \in \mathcal {B}  sämtlich dieselbe endliche Kardinalität \rho haben[27], findet man auch eine weitere Beschreibung der Hyperebenen, welche den Zusammenhang mit dem Hyperebenenbegriff der Geometrie augenfällig werden lässt. Hiernach ist nämlich eine Hyperebene H eines Matroids M charakterisierbar als eine maximale Teilmenge H \subsetneqq E des Ranges r(H) = \rho - 1.[28] Wegen dieses Zusammenhangs ist neben Hyperebene auch die Bezeichnung Copunkt geläufig.[29]

Die Hyperebenen eines Matroids legen dessen Struktur eindeutig fest, da sie per Komplementbildung umkehrbar eindeutig mit den Kreisen des dualen Matroids M^{*} verknüpft sind. Auf diesem Wege findet man, dass sich Matroidstrukturen auch festlegen lassen durch Hyperebenensysteme, also durch Systeme von Teilmengen, welchen den folgenden Hyperebenenaxiomen genügen.[30][31]

Hyperebenenaxiome[Bearbeiten | Quelltext bearbeiten]

Ein Teilmengensystem \mathcal{H} \subset \mathcal P(E) bildet genau dann das System der Hyperebenen eines Matroids über der Grundmenge E, wenn es den folgenden Bedingungen genügt:

(H1) E \notin \mathcal{H}
(H2) \forall H_1;H_2 \in \mathcal{H}  \colon ( H_1 \neq H_2 ) \Rightarrow  ( H_1 \subsetneqq H_2 )
(H3) \forall H_1;H_2 \in \mathcal{H} \, \forall x \in E \setminus (H_1 \cup H_2 ) \colon  \exists H_3 \in \mathcal{H}  \colon H_3 \supseteq (H_1 \cap H_2) \cup \{ x \}

Die ersten beiden Bedingungen besagen, dass \mathcal{H} eine Antikette bzgl. der Inklusionsrelation darstellt, welche aus lauter echten Teilmengen von E besteht. Das dritte Axiom formuliert eine Art Überdeckungsbedingung (engl. covering condition)[32]

Literatur[Bearbeiten | Quelltext bearbeiten]

  •  Martin Aigner: Kombinatorik. II Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07463-5. MR0460127
  • Hubertus Th. Jongen: Optimierung B. Skript zur Vorlesung, Verlag der Augustinus-Buchhandlung, Aachen, ISBN 3-925038-19-1
  • Bernhardt Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4. Auflage, Springer, Berlin 2007, ISBN 978-3-540-71843-7.
  • Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage, Vieweg-Teubner, Wiesbaden 2009, ISBN 978-3-8348-0629-1.
  • Joseph P. S. Kung: A Source Book in Matroid Theory. Springer Science+Business Media: New York, 1986.
  • P. Läuchli: Matroide, Eine Einführung für Mathematiker und Informatiker. Hochschulverlag vdf, Zürich 1998, ISBN 3-7281-2470-2
  • Jon Lee: A First Course in Combinatorial Optimization. In: Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge 2004, ISBN 0-521-01012-8.
  •  Giorgio Nicoletti, Neil White: Axiom Systems. In: Theory of Matroids. Edited by Neil White, University of Florida (= Encyclopedia of Mathematics and its Applications. 26). Cambridge University Press, Cambridge (u. a.) 1986, ISBN 0-521-30937-9, S. 29–44.
  • Hirokazu Nishimura, Susumu Kuroda: A Lost Mathematician, Takeo Nakasawa. The Forgotten Father of Matroid Theory. Birkhäuser: Basel, Boston, Berlin, 2009.
  • James Oxley: Matroid Theory. Oxford Mathematics 2004, ISBN 0-19-853563-5.
  • Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall Inc., Englewood Cliffs (NJ) 1982, ISBN 0-13-152462-3.
  •  D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. 8). Academic Press, London (u. a.) 1976, ISBN 0-12-744050-X.
  • D. J. A. Welsh: Matroids: Fundamental Concepts. In: R. L. Graham, M. Grötschel, L. Lovász (Hrsg.): Handbook of Combinatorics. Volume 1, MIT Press: Cambridge, 1995, S. 481–527.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise und Fußnoten[Bearbeiten | Quelltext bearbeiten]

  1. Hassler Whitney: On the abstract properties of linear dependence. In: Amer. J. Math. 57, 1935, S. 509–533.
  2. a b Leonid Mirsky, Hazel Perfect: Applications of the notion of independence to combinatorial analysis. In: J. Combinatorial Theory 2, 1967, S. 317–357.
  3. Henry H. Crapo und Gian-Carlo Rota:On the Foundations of Combinatorial Theory: Combinatorial Geometries. MIT Press: Cambridge, 1970.
  4. Paul M. Cohn: Universal Algebra. Harper & Row, 1965.
  5. Aigner: Kombinatorik II. S. 15–16.
  6. Hassler Whitney: On the abstract properties of linear dependence. In: Amer. J. Math. 57, 1935, S. 509–533.
  7. Bartel Leendert van der Waerden: Moderne Algebra. Springer: Berlin, 2. Auflage, 1937.
  8. Hirokazu Nishimura, Susumu Kuroda (Hrsg.): A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory. Birkhäuser: Basel, Boston, Berlin, 2009.
  9. Garrett Birkhoff: Abstract linear dependence in lattices. In: Amer. J. Math. 57, 1935, S. 800–801.
  10. Saunders MacLane: Some interpretations of abstract linear dependence in terms of projective geometry. In: Amer. J. Math. 58, 1936, 236-240.
  11. 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.
  12. Richard Rado: A theorem on independence relations. In: Quart. J. Math. 13, 1942, S. 83–89.
  13. Richard Rado: Axiomatic treatment of rank in infinite sets. In: Canad. J. Math. 1, 1949, S. 337–343.
  14. 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.
  15. Welsh: Matroids. In: Handbook of Combinatorics. S. 483.
  16. Jack Edmonds, Delbert R. Fulkerson: Transversals and matroid partition. In: J. Res. Nat. Bar. Stand. 69B, 1965, S. 147–153.
  17. Welsh: Matroid Theory. S. 6.
  18. a b 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.
  19. Die Notation der grundlegenden Definitionen orientiert sich an Oxley: Matroid Theory. S. 7–15.
  20. a b 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.
  21. Für einen Beweis der Kryptomorphie zwischen Unabhängigkeitsaxiomen und Basisaxiomen siehe z. B. Oxley: Matroid Theory. S. 16–18.
  22. Für einen Beweis der Kryptomorphie zwischen Unabhängigkeitsaxiomen und Kreisaxiomen siehe z. B. Oxley: Matroid Theory. S. 9–11.
  23. Für einen Beweis der Kryptomorphie zwischen Unabhängigkeitsaxiomen und Kreisaxiomen siehe Oxley: Matroid Theory. S. 9–10.
  24. Alexander von Felbert: Einführung in die Theorie der Matroide, In: mathematik-netz.de, 28.11.2007, S. 29; Oxley: Matroid Theory. S. 22.
  25. Alexander von Felbert: Einführung in die Theorie der Matroide. 2007, S. 31.
  26.  Welsh: S. 38.
  27. \rho nennt man auch den Rang von M und es ist dabei \rho = r(E) = r(M); vgl.  Aigner: S. 21.
  28.  Welsh: S. 38.
  29.  Aigner: S. 21.
  30.  Nicoletti-White: Axiom Systems. S. 37 ff.
  31.  Welsh: S. 35–39.
  32.  Welsh: S. 37.