Graph/Aufspannender Baum/Einführung/Textabschnitt

Definition

Ein Untergraph ${}B\subseteq G$ eines Graphen ${}G=(V,E)$ heißt aufspannender Baum von ${}G$, wenn ${}B$ ein Baum mit der vollen Knotenmenge ${}V$ ist.

Ein Graph, der einen aufspannenden Baum besitzt, ist zusammenhängend. Davon gilt auch die Umkehrung.

Satz

Ein zusammenhängender Graph

besitzt einen aufspannenden Baum.

Beweis

Wir führen Induktion über die Anzahl der Kanten. Der Induktionsanfang ist klar, da ein kantenfreier Graph nur im einpunktigen Fall zusammenhängend ist, und dies ein Baum ist. Sei ${}G=(V,E)$ ein zusammenhängender Graph mit ${}m$ Kanten. Wenn ${}G$ ein Baum ist, sind wir fertig. Es sei also ${}G$ kein Baum. Dann gibt es einen Kreis

$v_{1},v_{2},\ldots ,v_{r},v_{r+1}=v_{1}$

mit ${}r\geq 3$ in ${}G$. Wir betrachten den Graphen ${}G'$ mit der gleichen Knotenmenge ${}V$ und der neuen Kantenmenge

${}E'=E\setminus \{v_{1}v_{2}\}\,.$

Dieser Graph hat eine Kante weniger und er ist zusammenhängend, da der Zusammenhang zwischen ${}v_{1}$ und ${}v_{2}$ über das verbleibende „Kreissegment“ ${}v_{2},\ldots ,v_{r}=v_{1}$ gesichert ist. Nach Induktionsvoraussetzung gibt es einen aufspannenden Baum in ${}G'$, und dieser ist auch ein aufspannender Baum von ${}G$.

$\Box$

Dieser Beweis zeigt zugleich, wie man einen aufspannenden Baum in einem zusammenhängenden Graphen finden kann. Nach Fakt ist die Anzahl der Kanten in einem Spannbaum eindeutig bestimmt, sie ist um ${}1$ kleiner als die Knotenanzahl des Graphen. Insbesondere besitzt jeder Spannbaum die gleiche Kantenanzahl.

Beispiel

Wir betrachten den Spielzuggraphen des Turmes auf dem Schachbrett und interessieren uns für die Spannbäume darauf. Beispielsweise gibt es lineare Spannbäume, man kann ja die erste Zeile ablaufen, an deren Ende vertikal zur zweiten Zeile überwechseln und diese rückwärts durchlaufen u.s.w. Man kann auch „eckig spiralförmig“ lineare Spannbäume angeben. Nichtlineare Spannbäume erhält man, wenn man eine Zeile linear durchläuft und an jeden Punkt der Zeile linear eine Spalte anhängt. Diese Spannbäume verfügen alle über ${}63$ Kanten. Die angegebenen Bäume sind auch Spannbäume auf der gleichknotigen Menge, bei der nur geometrisch direkt (vertikal oder horizontal) nebeneinander liegende Felder durch eine Kante verbunden sind.