Beispiel für einen Vektormatroiden

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

Seien beispielsweise der ${\displaystyle \mathbb {R} }$-Vektorraum ${\displaystyle V=\mathbb {R} ^{3}}$ und als Grundmenge ${\displaystyle E}$ die Spalten der folgenden Matrix gegeben:

${\displaystyle A:={\begin{pmatrix}1&0&0&0&0&0\\0&1&0&{\frac {1}{2}}&1&0\\0&0&1&{\frac {1}{2}}&1&0\end{pmatrix}}}$

Die entsprechenden Spaltenvektoren werden wie folgt bezeichnet:

${\displaystyle 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\\{\frac {1}{2}}\\{\frac {1}{2}}\end{pmatrix}},e:={\begin{pmatrix}0\\1\\1\end{pmatrix}},f:={\begin{pmatrix}0\\0\\0\end{pmatrix}}}$

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

${\displaystyle {\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 ${\displaystyle 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 ${\displaystyle f}$.
• Zwei oder mehrere Vektoren sind skalare Vielfache voneinander. Im Beispiel sind dies Mengen mit den Vektoren ${\displaystyle d}$ und ${\displaystyle e}$ und alle Mengen, die den Vektor ${\displaystyle f}$ enthalten.

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

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

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

Beispiel für ein graphisches Matroid

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

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

In diesem Beispiel entsprechen die kreisfreien Teilgraphen unabhängigen Mengen ${\displaystyle {\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 ${\displaystyle {\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:

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

Unabhängigkeitsaxiome

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

(I1) ${\displaystyle \emptyset \in {\mathcal {I}}}$.

(I2) Wenn ${\displaystyle I\in {\mathcal {I}}}$ und ${\displaystyle I'\subseteq I}$, dann ist ${\displaystyle I'\in {\mathcal {I}}}$.

(I3) Wenn ${\displaystyle I_{1}}$ und ${\displaystyle I_{2}}$ in ${\displaystyle {\mathcal {I}}}$ sind und ${\displaystyle \left|I_{1}\right|<\left|I_{2}\right|}$, dann gibt es ein Element ${\displaystyle e}$ aus ${\displaystyle I_{2}-I_{1}}$, so dass ${\displaystyle I_{1}\cup \{e\}\in {\mathcal {I}}.}$

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

Basisaxiome

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

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

(B1) ${\displaystyle {\mathcal {B}}\neq \emptyset }$

(B2) Für Basen ${\displaystyle B_{1}}$ und ${\displaystyle B_{2}}$ von ${\displaystyle {\mathcal {B}}}$ und jedes ${\displaystyle x\in B_{1}-B_{2}}$ gibt es ein ${\displaystyle y\in B_{2}-B_{1}}$, sodass ${\displaystyle (B_{1}-\{x\})\cup \{y\}\in {\mathcal {B}}}$.

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

Zwei Basen eines Matroids besitzen stets dieselbe Kardinalität: Wenn ${\displaystyle B_{1}}$ und ${\displaystyle B_{2}}$ Basen eines Matroids ${\displaystyle M}$ sind, dann gilt ${\displaystyle |B_{1}|=|B_{2}|}$.

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

Kreisaxiome

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

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

(C1) ${\displaystyle \emptyset \notin {\mathcal {C}}}$.

(C2) Wenn ${\displaystyle C_{1},C_{2}\in {\mathcal {C}}}$ und ${\displaystyle C_{1}\subseteq C_{2}}$, dann folgt ${\displaystyle C_{1}=C_{2}}$.

(C3) Für alle ${\displaystyle C_{1},C_{2}\in {\mathcal {C}}}$ mit ${\displaystyle C_{1}\neq C_{2}}$ und ${\displaystyle e\in C_{1}\cap C_{2}}$ gibt es ${\displaystyle C_{3}\in {\mathcal {C}}}$, sodass ${\displaystyle 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 ${\displaystyle {\mathcal {C}}}$ die Kreise des zugrundeliegenden Graphen enthalten, woher auch die Bezeichnung stammt. Die Eigenschaft (C3) wird auch (schwaches) Kreiseliminationsaxiom genannt: Zu je zwei verschiedenen Kreisen ${\displaystyle C_{1}}$ und ${\displaystyle C_{2}}$ und einem Element ${\displaystyle e}$ aus dem Schnitt dieser beiden Kreise, gibt es einen dritten Kreis ${\displaystyle C_{3}}$, der in den beiden Kreisen ${\displaystyle C_{1}}$ und ${\displaystyle C_{2}}$ enthalten ist und das gewählte Element ${\displaystyle e}$ aus dem Schnitt vermeidet.

Axiome der Rangfunktion

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

Für ein Matroid ${\displaystyle M=(E,{\mathcal {I}})}$ definiert man seine Rangfunktion ${\displaystyle r:{\mathcal {P}}(E)\to \mathbb {N} _{0}}$ als

${\displaystyle X\mapsto r(X):=|B_{X}|}$ für ein ${\displaystyle B_{X}\in {\mathcal {B}}({\mathcal {I}}|X)}$.

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

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

(R1) Wenn ${\displaystyle X\subseteq E}$, dann ${\displaystyle 0\leq r(X)\leq |X|}$.

(R2) Wenn ${\displaystyle X\subseteq Y\subseteq E}$, dann ${\displaystyle r(X)\leq r(Y)}$.

(R3) Für alle ${\displaystyle X,Y\in E}$ gilt: ${\displaystyle r(X\cup Y)+r(X\cap Y)\leq r(X)+r(Y)}$.

Die Rangfunktion ${\displaystyle 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 ${\displaystyle M}$ ein Matroid mit Rangfunktion ${\displaystyle r}$ und sei ${\displaystyle X\subseteq E(M)}$. Dann gilt

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

Axiome des Hüllenoperators

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

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

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

Der Hüllenoperator eines Matroids ${\displaystyle M}$ auf einer Grundmenge ${\displaystyle E}$ hat nun folgende Eigenschaften:

(CL1) Wenn ${\displaystyle X\subseteq E}$, dann ${\displaystyle X\subseteq cl(X)}$.

(CL2) Wenn ${\displaystyle X\subseteq Y\subseteq E}$, dann ${\displaystyle cl(X)\subseteq cl(Y)}$.

(CL3) Wenn ${\displaystyle X\subseteq E}$, dann ${\displaystyle cl(cl(X))=cl(X)}$.

(CL4) Wenn ${\displaystyle X\subseteq E}$, ${\displaystyle x\in E}$ und ${\displaystyle y\in cl(X\cup x)-cl(X)}$, dann ${\displaystyle x\in cl(X\cup y)}$.

Für ein gegebenes Matroid ${\displaystyle M}$ mit Hüllenoperator ${\displaystyle cl}$ sind die Basen des Matroids gerade die (bzgl. ${\displaystyle \subseteq }$) minimalen Mengen ${\displaystyle B}$ mit ${\displaystyle cl(B)=E}$.

Hyperebenenaxiome

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

(H1) ${\displaystyle E\notin {\mathcal {H}}}$

(H2) ${\displaystyle \forall H_{1};H_{2}\in {\mathcal {H}}\colon (H_{1}\neq H_{2})\Rightarrow (H_{1}\nsubseteq H_{2})}$

(H3) ${\displaystyle \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 ${\displaystyle {\mathcal {H}}}$ eine Antikette bzgl. der Inklusionsrelation darstellt, welche aus lauter echten Teilmengen von ${\displaystyle E}$ besteht. Das dritte Axiom formuliert eine Art Überdeckungsbedingung (englisch covering condition)