Beschreibung
Ein Maximaler Baum ist eine Teilgraph eines Graph mit der Form eines Baumes, der nicht vergrößert werden kann.
Definition
Sei ein Graph. Die Menge aller Teilgraphen, die Bäume sind, können nach geordnet werden. Nach Zorns Lemma gibt es demnach Maximale Bäume.
Eigenschaften
Enthält alle Knoten eines zusammenhängenden Graphen
Sei ein Zusammenhängener Graph. Dann enthält ein maximaler Baum des Graphen alle Knoten.