Zusammenhängender Graph/Aufspannender Baum/Minimal zusammenhängend/Aufgabe

< Zusammenhängender Graph < Aufspannender Baum < Minimal zusammenhängend

Es sei ${}G$ ein zusammenhängender Graph. Zeige, dass für einen Untergraphen ${}H=(V,F)\subseteq G$ (also mit voller Vertexmenge) die folgenden Aussagen äquivalent sind.

${}H$ ist ein Baum.
${}H$ ist ein aufspannender Baum.
${}H$ ist maximal kreisfrei, d. h. sobald man eine Kante aus ${}G$ zu ${}H$ hinzutut, entsteht ein Kreis.
${}H$ ist minimal zusammenhängend, d. h. sobald man eine Kante herausnimmt, wird der Graph unzusammenhängend.

Eine Lösung erstellen

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