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.

Ungerichteter Baum mit vier inneren Knoten (schwarz) und fünf Blättern (weiß)

Paarweise äquivalente Charakterisierungen

Ungerichtete Bäume sind einfache zusammenhängende Graphen die eine der folgenden äquivalenten Bedingungen erfüllen.

1. Sie haben keinen Kreis.
2. Je zwei beliebige verschiedene Knoten sind durch genau einen Pfad verbunden.
3. Die Anzahl der Knoten ist um 1 größer als die Anzahl der Kanten.