Ungerichteter Baum

Ein ungerichteter Baum ist in der Graphentheorie ein spezieller Graph. Ungerichtete Bäume lassen sich durch folgende äquivalente Definitionen charakterisieren.

Definition

Ungerichtete Bäume sind einfache zusammenhängende Graphen

1. ohne Kreis,
2. in denen je zwei beliebige verschiedene Knoten durch höchstens einen Pfad verbunden sind oder
3. die Anzahl der Knoten um 1 größer ist als die Anzahl der Kanten.

Weitere Begriffe

In ungerichteten Bäumen gibt es im Gegengsatz zu gewurzelten Bäumen 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.

See also: Ungerichteter Baum, Einfacher Graph, Gewurzelter Baum, Grad (Graphentheorie), Graph (Graphentheorie), Graphentheorie, Kante (Graphentheorie), Knoten (Graphentheorie), Kreis (Graphentheorie), Maximalgrad