Graph/Aufspannender Baum/Einführung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Ein Untergraph eines Graphen heißt aufspannender Baum von , wenn ein Baum mit der vollen Knotenmenge ist.

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



Satz  

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 ein zusammenhängender Graph mit Kanten. Wenn ein Baum ist, sind wir fertig. Sei also kein Baum. Dann gibt es einen Kreis

mit in . Wir betrachten den Graphen mit der gleichen Knotenmenge und der neuen Kantenmenge

Dieser Graph hat eine Kante weniger und er ist zusammenhängend, da der Zusammenhang zwischen und über das verbleibende „Kreissegment“ gesichert ist. Nach Induktionsvoraussetzung gibt es einen aufspannenden Baum in , und dieser ist auch ein aufspannender Baum von .


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 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 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.