Aufspannender Baum/Rekursionsformel/1/Beispiel

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Deletion-contraction.svg

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.