Height (graph theory)
In graph theory , one can assign a height to a non-empty finite root tree . This assignment is defined as the maximum possible length of a path that ends in the root . Depending on whether this length is measured by the number of edges or the number of nodes, the height can differ depending on the underlying definitions. Whether the root itself should be counted when determining the number of nodes also differs from author to author. Apart from the definition differences, this assignment is unique because in finite sets of natural numbers (the possible path lengths are nothing else) the maxima are unique. These paths remain finite because trees, and especially root trees, cannot contain a self-contained sequence of edges ( circles ).
For a node of non-empty finite root trees, a height can be explained as follows:
- Remove the (clearly determined) shortest path from the node to the root, except for the node itself.
- Remove all nodes and edges that can be reached from the root, including the root.
The height of the resulting residual graph is explained as the height of the node.
Overall, the height can thus be understood as a surjective mapping from the nodes into the natural numbers up to a certain limit.
In many search trees the height is explicitly stored for each node so that it does not have to be calculated every time it is called up. This can be particularly useful with inductively declared data structures . Some verifications of properties of acyclic graphs work with an induction proof over a height function of a suitable root tree explained in this way.