Graph/Aufspannender Baum/Matroid/Textabschnitt

Definition

Ein Untergraph ${}W\subseteq G$ eines Graphen ${}G=(V,E)$ heißt aufspannender Wald von ${}G$, wenn ${}W$ ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von ${}V$ übereinstimmen.

Ein aufspannender Wald ist also dadurch gekennzeichnet, dass er auf jeder Zusammenhangskomponenten von ${}G$ ein aufspannender Baum ist. Insbesondere ist ein aufspannender Wald knotengleich zu ${}G$ und er lässt sich nicht zu einem Unterwald von ${}G$ vergrößern.

Wir bezeichnen die Menge der Wälder in einem Graphen ${}G=(V,E)$, die ${}V$ als Knotenmenge besitzen, mit ${}{\mathcal {W}}(G)$. Ein solcher Wald ist durch seine Kanten festgelegt, da ja die Knotenmenge mit der von ${}G$ übereinstimmt. Insbesondere gehört jeder aufspannende Wald von ${}G$ zu ${}{\mathcal {W}}(G)$, aber auch der kantenfreie Graph auf ${}V$ gehört dazu. Es gibt natürlich auch Wälder in ${}G$, deren Knotenmenge kleiner ist, das folgende Lemma gilt auch für sie.

Lemma

Es sei ${}G=(V,E)$ ein Graph mit ${}n$ Knotenpunkten und ${}c$ Zusammenhangskomponenten.

Dann lässt sich jeder Unterwald ${}(W,F)\subseteq (V,E)$ mit weniger als ${}n-c$ Kanten zu einem Unterwald mit ${}n-c$ Kanten ergänzen.

Beweis

Wir zeigen, dass wir den Wald unter der vorgegebenen Bedingung um eine Kante (eventuell unter Hinzunahme von weiteren Knotenpunkten) zu einem größeren Wald ergänzen können. Jede Zusammenhangskomponente des Waldes ${}(W,F)$ liegt ganz in einer Zusammenhangskomponente von ${}G$. Nach Fakt gilt die Voraussetzung entsprechend in mindestens einer Zusammenhangskomponente von ${}G$, d.h. wir können annehmen, dass ${}G$ zusammenhängend ist. Es sei

${}(B,H)\subseteq (W,F)\,$

ein Baum von ${}W$ (wenn ${}W$ leer ist, so können wir direkt zu einem einpunktigen Baum übergehen). Dieser besitzt weniger als ${}n-1$ Elemente. Sei ${}v\in V$ ein Punkt, der nicht in ${}B$ vorkommt. Es gibt einen Weg ${}u=u_{1},\ldots ,u_{n}=v$ in ${}G$ mit ${}u\in B$. Dabei findet irgendwo längs des Weges der Übergang von ${}B$ zu nicht ${}B$ statt, d.h. man kann davon ausgehen, dass ${}u_{2}=v\notin B$ ist. Wir nehmen die Kante ${}\{u,v\}$ (und eventuell den Punkt ${}v$) zu ${}W$ hinzu und müssen begründen, dass dies nach wie vor ein Wald ist. Bei ${}v\notin W$ ist

${}(B',H')=(B\cup \{v\},H\cup \{u,v\})\,$

nach Fakt ein größerer Baum, da ja ${}v$ ein Blatt von ${}B'$ ist. Bei ${}v\in W$ wird ${}B$ mit einem anderen Baum aus ${}W$ vereinigt, was wieder einen Baum ergibt.

$\Box$

Satz

Zu einem Graphen ${}G=(V,E)$ ist die Waldmenge ${}{\mathcal {W}}(G)$ (mit der vollen Knotenmenge)

ein Matroid auf ${}E$.

Der Rang dieses Matroids ist die Anzahl der Kanten in einem aufspannenden Wald.

Beweis

Wir gehen die Axiome für ein Matroid durch. Die Menge ${}(V,\emptyset )$ ist ein Wald, bestehend aus den einpunktigen Bäumen. Ein Untergraph eines Waldes ist wieder ein Wald. Es seien nun ${}W$ und ${}Z$ Wälder von ${}G$ und ${}Z$ enthalte eine Kante mehr als ${}W$. Es ist zu zeigen, dass man ${}W$ durch eine Kante aus ${}E$ zu einem größeren Wald ergänzen kann. Da aber die Anzahl der Kanten von ${}Z$ durch die Zahl aus Fakt beschränkt ist, folgt aus dieser Aussage, dass man ${}W$ vergrößern kann.

$\Box$

Mit dem Sprachgebrauch der Matroidtheorie kann man sagen, dass die Wälder den unabhängigen Untergraphen und die aufspannenden Wälder den maximal unabhängigen Untergraphen, also den Basen, entsprechen, wobei unabhängig im graphentheoretischen Kontext als zykelfrei zu verstehen ist.