Graph/Aufspannender Baum/Matroid/Textabschnitt
Ein Untergraph eines Graphen heißt aufspannender Wald von , wenn ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von übereinstimmen.
Ein aufspannender Wald ist also dadurch gekennzeichnet, dass er auf jeder Zusammenhangskomponenten von ein aufspannender Baum ist. Insbesondere ist ein aufspannender Wald knotengleich zu und er lässt sich nicht zu einem Unterwald von vergrößern.
Wir bezeichnen die Menge der Wälder in einem Graphen , die als Knotenmenge besitzen, mit . Ein solcher Wald ist durch seine Kanten festgelegt, da ja die Knotenmenge mit der von übereinstimmt. Insbesondere gehört jeder aufspannende Wald von zu , aber auch der kantenfreie Graph auf gehört dazu. Es gibt natürlich auch Wälder in , deren Knotenmenge kleiner ist, das folgende Lemma gilt auch für sie.
Es sei ein Graph mit Knotenpunkten und Zusammenhangskomponenten.
Dann lässt sich jeder Unterwald mit weniger als Kanten zu einem Unterwald mit Kanten ergänzen.
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 liegt ganz in einer Zusammenhangskomponente von . Nach Fakt gilt die Voraussetzung entsprechend in mindestens einer Zusammenhangskomponente von , d.h. wir können annehmen, dass zusammenhängend ist. Es sei
ein Baum von (wenn leer ist, so können wir direkt zu einem einpunktigen Baum übergehen). Dieser besitzt weniger als Elemente. Sei ein Punkt, der nicht in vorkommt. Es gibt einen Weg in mit . Dabei findet irgendwo längs des Weges der Übergang von zu nicht statt, d.h. man kann davon ausgehen, dass ist. Wir nehmen die Kante (und eventuell den Punkt ) zu hinzu und müssen begründen, dass dies nach wie vor ein Wald ist. Bei ist
nach Fakt ein größerer Baum, da ja ein Blatt von ist. Bei wird mit einem anderen Baum aus vereinigt, was wieder einen Baum ergibt.
Wir gehen die Axiome für ein Matroid durch. Die Menge ist ein Wald, bestehend aus den einpunktigen Bäumen. Ein Untergraph eines Waldes ist wieder ein Wald. Es seien nun und Wälder von und enthalte eine Kante mehr als . Es ist zu zeigen, dass man durch eine Kante aus zu einem größeren Wald ergänzen kann. Da aber die Anzahl der Kanten von durch die Zahl aus Fakt beschränkt ist, folgt aus dieser Aussage, dass man vergrößern kann.
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.