- Ungerichteter Baum
-
Ein ungerichteter Baum ist in der Graphentheorie ein spezieller Baum, dessen Kanten keine ausgezeichnete Richtung besitzen. Im Gegensatz zu gewurzelten Bäumen mit Kantenrichtungen besitzen ungerichtete Bäume keine ausgezeichnete Wurzel. Es lassen sich lediglich Blätter identifizieren, die dadurch charakterisiert sind, dass sie nur genau einen Nachbarn besitzen, deren Grad also genau 1 ist. Als Ordnung bezeichnet man hier den Maximalgrad des Baumes. Als innere Knoten bezeichnet man alle Knoten, die keine Blätter sind.
Paarweise äquivalente Charakterisierungen
Ungerichtete Bäume sind einfache zusammenhängende Graphen
Wikimedia Foundation.