Multigraph/Aufspannender Baum/Rekursionsformel/Fakt

Rekursionssatz für aufspannende Bäume

Es sei ${}G$ ein schleifenfreier Multigraph und ${}e$ eine Kante von ${}G$ .

Dann besteht für die Anzahl der aufspannenden Bäume der Zusammenhang

${}t(G)=t(G\setminus e)+t(G/e)\,.$

Zum Beweis, Alternativen Beweis erstellen

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.