< Aufspannender Baum < Rekursionsformel < 1
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.
This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.