Leaf node
In graph theory, the node with exactly one neighbor of a leaf or terminal node ( leaf engl. ) and the nodes in a tree with more than one neighbor as the internal nodes or non- terminal nodes ( engl. inner vertex ) refers. The classification of roots and isolated nodes depends on the particular definition.
Definition
Usual definitions of leaves and intrinsic nodes in a tree are for example:
- " The corners [ node ] of degree 1 in a tree are its leaves "
- " The nodes of a tree of degree 1 are called leaves, the nodes of degree greater than 1 are called inner nodes " ( Meinel and Mundhenk, 2006, page 260)
- " A corner with out-degree 0 is called a leaf of the tree. The other vertices are called inner corners " ( Turau, 2004, page 53)
The exact wording depends among other things on whether the definition of directed trees (ie trees with a root ) or for undirected trees is to apply. When looking tree, the root is often excluded as a special case of the definition. Likewise, most definitions do not apply to the special case of an isolated node, ie a tree that consists of only one node.
Special cases
Depending on whether the isolated nodes and roots to be construed as a sheet (and optionally the roots of internal nodes ) or as a special case, the following definitions are possible. For undirected trees, only the first row is relevant. The special case of an isolated node can for instance be eliminated by requiring that a tree of at least two nodes must exist.
History
Trees as mathematical structures was introduced in 1857 by Arthur Cayley. Cayley shall in only on rooted trees. He first distinguishes three types of nodes ( "either the root Itself, or proper knots or the extremities of the free branches " ) and later the two types of "terminal knot" (leaf) and "non -terminal knot" (internal nodes). His second article on the theory of trees contains a list of all possible trees with one, two, three or four leaves.
.
For the number of trees with m leaves he derives a formula that corresponds to sequence A000670 in OEIS.