Aufspannender Baum/Rekursionsformel/1/Beispiel

Aus Wikiversity

Wir betrachten den Diamantgraphen und führen die Kontraktionen und Herausnahmen wie im Bild durch. Dieser Algorithmus liefert letztlich lineare Graphen, die jeweils einen Spannbaum haben (und einen Spannbaum des ursprünglichen Graphen repräsentieren). Nach Fakt gibt es also Spannbäume.