Höhe (Graphentheorie)

In der Graphentheorie kann man zu einem nichtleeren endlichen Wurzelbaum eine Höhe zuordnen. Diese Zuordnung ist als die maximal mögliche Länge eines Weges, der in der Wurzel endet, definiert. Je nachdem, ob man diese Länge an der Kantenzahl, oder an der Knotenzahl misst, kann sich die Höhe in Abhängigkeit von der zugrundegelegten Definitionen unterscheiden. Auch, ob die Wurzel selbst beim Bestimmen der Knotenzahl mitgezählt werden soll, unterscheidet sich von Autor zu Autor. Abgesehen von den Definitionsunterschieden ist diese Zuordnung aber eindeutig, weil in endlichen Mengen natürlicher Zahlen (nichts anderes sind die möglichen Weglängen) die Maxima eindeutig sind. Diese Wege bleiben endlich, weil Bäume, und Wurzelbäume insbesondere, keine in sich geschlossene Kantenfolge (Kreis) enthalten können.