Graph/Baum/Charakterisierung/Fakt

Charakterisierungssatz für Bäume

Es sei ${}G=(V,E)$ ein Graph mit nichtleerer Knotenmenge ${}V$ . Dann sind folgende Aussagen äquivalent.

${}G$ ist ein Baum.

Zwischen je zwei Punkten ${}u,v\in V$ gibt es einen eindeutigen Verbindungsweg ohne Wiederholung.

${}G$ ist zusammenhängend und es gilt ${}{\#\left(E\right)}={\#\left(V\right)}-1$ .

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.