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.

Definition[Bearbeiten]

Sei E eine Menge und \mathcal U \subseteq \mathcal P(E) ein Mengensystem über E. Das Paar M = (E;\mathcal U) heißt Matroid, falls folgende Bedingungen erfüllt sind:

1. \emptyset \in \mathcal U
2. \forall A \in \mathcal U  \forall B \in \mathcal P(E) \colon B \subseteq A \Rightarrow B \in \mathcal U
3. \forall A; B \in \mathcal U \colon \left| B \right| < \left| A\right| \Rightarrow (\exists x \in A \setminus B \colon B \cup \{x\} \in \mathcal U)
4. \exists n\in \N \colon \forall A \in \mathcal U \colon |A|\leq n

Dabei ist \left| A \right| die Kardinalität der Menge A.

Die Elemente von E heißen die Punkte, die Elemente von \mathcal U die unabhängigen Teilmengen von M, Mengen aus \mathcal P(E) \setminus \mathcal U werden abhängig genannt.

Genügt M nur den ersten beiden Eigenschaften, so bildet es ein Unabhängigkeitssystem.

Das kleinste n, das die vierte Bedingung erfüllt, nennt man den Rang des Matroides.

Austauscheigenschaft[Bearbeiten]

Das Alleinstellungsmerkmal eines Matroides gegenüber einem gewöhnlichen Unabhängigkeitssystem besteht in der Austauscheigenschaft[1], also der dritten Bedingung obiger Definition. Während sich die ersten beiden Axiome leicht als Forderungen der Existenz mindestens einer unabhängigen Menge und der Abgeschlossenheit des Systems \mathcal U 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 A zu einer (kleineren) unabhängigen Menge B hinzufügen. Deshalb spricht man auch von der Vergrößerungseigenschaft (von engl. augmentation property[2]). Von der so erzeugten Menge weiß man, dass sie ebenfalls wieder unabhängig ist. Sie enthält nun zwar Elemente der Menge A, allerdings wurden im Vergleich zu dieser die übrigen enthaltenen Punkte durch Elemente aus B \backslash A ersetzt. Dies begründet wiederum den Namen Austauscheigenschaft.

Beispiele[Bearbeiten]

  • Den Prototyp eines Matroides bilden die Spalten einer Matrix - daher der Name - bzw. jedes andere endliche Vektorsystem mit der Gesamtheit der linear unabhängigen Teilsysteme als unabhängige Teilmengen.
  • Die Kantenmenge eines endlichen Graphen zusammen mit den kreisfreien Teilmengen bilden das sogenannte graphische Matroid.
    • Dessen maximal unabhängigen Mengen sind dann genau die aufspannenden Wälder des zugrundeliegenden Graphen.

Alternative Charakterisierungen eines Matroids[Bearbeiten]

Die Anwendungen von Matroiden in den verschiedenen mathematischen Teildisziplinen haben die Definition weiterer Mengensysteme über bzw. Funktionen auf der Grundmenge E motiviert. Umgekehrt charakterisieren diese das unterliegende Matroid vollständig, d.h. aus jedem der neuen Systeme lässt sich wieder eine Menge \mathcal U derart definieren, dass (E;\mathcal U) zu einem Matroid wird.

Kreise[Bearbeiten]

Eigenschaft 3: Auch ohne die ge­strichelte Kante enthält die Menge noch einen Kreis.

Sei \mathcal K \subseteq \mathcal P(E) ein Mengensystem, es heiße Kreissystem über E, wenn es folgenden Bedingungen genügt:

  1. \emptyset \notin \mathcal K
  2. \forall A \in \mathcal P(E) \colon (\exists K \in \mathcal K \colon A \subsetneq K) \Rightarrow A \notin \mathcal K
  3. \forall K_1;K_2 \in \mathcal K; x \in K_1 \cap K_2 \colon \exists K \in \mathcal K \colon K \subseteq (K_1 \cup K_2) \setminus \{x\}

Die minimal abhängigen Teilmengen eines Matroides bilden stets ein Kreissystem. Besonders anschaulich wird dies in graphischen Matroiden, da dort die Elemente von \mathcal K genau die Kreise des zugrundeliegenden Graphens sind, woher auch die Bezeichnung stammt.

Eine Menge ist genau dann unabhängig, wenn sie kreisfrei ist. Ist also \mathcal K ein nicht-leeres Kreissystem über einer Menge E, so bildet umgekehrt (E;\mathcal U) mit \mathcal U = \{A \subseteq E | \nexists K \in \mathcal K \colon K \subseteq A\} ein Matroid derart, dass die minimalen Elemente von \mathcal P(E) \setminus \mathcal U gerade die Kreise aus \mathcal K sind.

Basen[Bearbeiten]

Sei \emptyset\neq\mathcal B \subseteq \mathcal P(E) wieder ein Mengensystem, es wird Basissystem genannt, wenn folgendes gilt:

\forall B_1;B_2 \in \mathcal B; x \in B_1 \setminus B_2 \colon \exists y \in B_2 \setminus B_1 \colon (B_1 \cup \{y\}) \setminus \{x\} \in \mathcal B

Die maximal unabhängigen Teilmengen eines Matroides bilden ein Basissystem. Für endlichdimensionale Vektorräume fällt dies mit dem klassischen Basisbegriff zusammen und die definierende Eigenschaft entspricht dem Austauschlemma von Steinitz.

Es lässt sich zeigen, dass alle Elemente von \mathcal B dieselbe Mächtigkeit besitzen müssen, sie ist gleich dem oben definierten Rang des Matroides.

Ist wiederum \mathcal B ein nicht-leeres Basissystem über einer Menge E, so wird diese durch \mathcal U = \{A \subseteq E | \exists B \in \mathcal B \colon A \subseteq B\} zu einem Matroid und die maximalen Elemente in \mathcal U sind genau die Basen aus \mathcal B.

Rangfunktion[Bearbeiten]

Eine Abbildung r \colon \mathcal P(E) \to \N sei eine Rangfunktion über E, wenn sie folgende Eigenschaften erfüllt:

  1. \forall A \subseteq E\colon 0 \le r(A) \le \left| A \right|
  2. \forall A,B \subseteq E\colon A \subseteq B \Rightarrow r(A) \le r(B)
  3. \forall A,B \subseteq E\colon r(A \cap B) + r(A \cup B) \le r(A) + r(B)

Alternativ dazu findet man folgende äquivalente Definition:

  1. r\left(\emptyset\right)=0
  2. \forall X\subseteq E, y\in E\colon r\left(X\right)\leq r\left(X\cup\left\{x\right\}\right)\leq r\left(X\right)+1
  3. \forall X\subseteq E, x,y\in E\colon r\left(X\cup\left\{x\right\}\right)=r\left(X\cup\left\{y\right\}\right)=r\left(X\right)\Rightarrow r\left(X\cup\left\{x,y\right\}\right)=r\left(X\right)

Für ein Matroid M=(E;\mathcal U) und eine Teilmenge F \subseteq E ist (F;\mathcal U_F = \{A \in \mathcal U | A \subseteq F \}) wieder ein (Unter-)Matroid. Es sei r(F) sein Rang (alternativ: r(F)=\max \left\{|A|\colon A\in\mathcal U , A\subseteq F  \right\}), dann ist r die Rangfunktion von M. Im ersten Beispiel oben entspricht der Rang einer Menge von Vektoren der Dimension ihrer linearen Hülle.

Analog bilden die Teilmengen A \subseteq E mit r(A) = \left| A \right| für eine Rangfunktion r im obigen Sinne ein System \mathcal U unabhängiger Mengen und r wird zur Rangfunktion des entstehenden Matroides.

Hüllenoperator[Bearbeiten]

Für ein Matroid (E;\mathcal U) mit der Rangfunktion r \colon \mathcal P(E) \to \N ist durch s(A) = \{x\in E\mid r(A\cup\{x\}) = r(A)\} für eine Teilmenge A\subseteq E ein Hüllenoperator s \colon \mathcal P(E) \to \mathcal P(E) mit der zusätzlichen Eigenschaft

\forall A \in \mathcal P(E);x;y \in E \colon ( y \notin s(A) \and y \in s(A \cup \{x\})) \Rightarrow x \in s(A \cup \{y\})

erklärt. Er entspricht der Bildung der linearen Hülle im Beispiel oben.

Ist s ein Hüllenoperator über der Menge E mit dieser Zusatzeigenschaft, so wird die Grundmenge mit \mathcal U = \{A \subseteq E | \forall x \in A \colon s(A \setminus \{x\}) \neq s(A) \} als System unabhängiger Teilmengen zu einem Matroiden, dessen zugehöriger Hüllenoperator wieder s ist.

Greedy-Algorithmen[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.[1]

Matroide und Hyperebenen[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:[3]

  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[4] , 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 charakterierbar als ein maximale Teilmenge H \subsetneqq E des Ranges r(H) = \rho - 1.[5] Wegen dieses Zusammenhangs ist neben Hyperebene auch die Bezeichnung Copunkt geläufig.[6]

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.[7][8]

Hyperebenenaxiome[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)[9]

Literatur[Bearbeiten]

  •  Martin Aigner: Kombinatorik. II Matroide und Transversaltheorie (= Hochschultext). Springer Verlag, Berlin (u. a.) 1976, ISBN 3-540-07463-5. MR0460127
  • James Oxley: Matroid Theory. Oxford Mathematics 2004, ISBN 0-19-853563-5.
  • Bernhardt Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4. Auflage, Springer, Berlin 2007, ISBN 978-3-540-71843-7.
  • Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall Inc., Englewood Cliffs (NJ) 1982, ISBN 0-13-152462-3.
  • Jon Lee: A First Course in Combinatorial Optimization. In: Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge 2004, ISBN 0-521-01012-8.
  • Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage, Vieweg-Teubner, Wiesbaden 2009, ISBN 978-3-8348-0629-1.
  • Hubertus Th. Jongen: Optimierung B. Skript zur Vorlesung, Verlag der Augustinus-Buchhandlung, Aachen, ISBN 3-925038-19-1
  • P. Läuchli: Matroide, Eine Einführung für Mathematiker und Informatiker. Hochschulverlag vdf, Zürich 1998, ISBN 3-7281-2470-2
  •  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.
  •  D. J. A. Welsh: Matroid Theory (= L.M.S. Monographs. 8). Academic Press, London (u. a.) 1976, ISBN 0-12-744050-X.

Weblinks[Bearbeiten]

Einzelnachweise und Fußnoten[Bearbeiten]

  1. a b G. Meyer: Vorlesung: Algorithmen und Datenstrukturen 2; Universität Leipzig; Wintersemester 2000.
  2. 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.
  3.  Welsh: S. 38.
  4. \rho nennt man auch den Rang von M und es ist dabei \rho = r(E) = r(M); vgl.  Aigner: S. 21.
  5.  Welsh: S. 38.
  6.  Aigner: S. 21.
  7.  Nicoletti-White: Axiom Systems. S. 37 ff.
  8.  Welsh: S. 35 - 39.
  9.  Welsh: S. 37.