Leaves and Inner Nodes in Graph Theory

from Wikipedia, the free encyclopedia
Examples
Unoriented tree
Unoriented tree
Directed tree (here: Out-Tree )
Directed tree
Legend
leaf ○
Inner knot ●
root ◉ or ◎

In the graph theory be in a tree the nodes with exactly one neighbors as leaf or end node ( English leaf ; also referred to as outer or external nodes hereinafter) and the nodes with more than one neighbors as internal or interior node or non-leaf ( English intra- vertex ). The classification of roots and isolated nodes depends on the respective definition.

definition

Common definitions of leaves and inner nodes in a tree include:

  • "The corners [nodes] of degree 1 of 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, p. 260).
  • “A corner with an initial degree of 0 is called a leaf of the tree. The other corners are called inner corners ”(Turau, 2004, page 53).

The exact wording depends, among other things, on whether the definition is to apply to directed trees (i.e. trees with one root) or to undirected trees . In the case of a directed tree, the root is often excluded from the definition as a special case. Likewise, most of the definitions do not apply to the special case of an isolated node, i.e. a tree that only consists of one node.

special cases

The following definitions are possible, depending on whether isolated nodes and roots are interpreted as leaves (and, if applicable, roots as inner nodes) or as a special case. Only the first row is relevant for undirected trees. The special case of isolated nodes can be eliminated, for example, by requiring that a tree must consist of at least two nodes.

Isolated node or root
leaf Not a sheet
Root with
degree of exit 1 		leaf A leaf is a knot of degree less than 2. All other knots are inner knots. A leaf is a node of degree 1. Nodes of degree greater than 1 are inner nodes.
Inner knot A leaf is a node of degree 0. All other nodes are inner nodes. A leaf is a node with exit degree 0 and entrance degree 1. An inner node is a node with exit degree greater than 0.
Special case A leaf is a node with degree of exit 0. All other nodes except the root are inner nodes. A leaf is a degree 1 knot. All other knots are inner knots. The root is excluded from this definition.

history

Trees as mathematical structures was introduced by Arthur Cayley in 1857 . Cayley only goes into rooted trees. He first differentiates between three types of knots ("either the root itself, or proper knots or the extremities of the free branches") and later the two types "terminal knot" (leaf) and "non-terminal knot" (inner knot). His second article on the theory of trees lists all possible trees with one, two, three or four leaves.

Possible trees with one to four leaves (Cayley, 1859)

For the number of trees with m leaves he derives a formula that corresponds to sequence A000670 in OEIS .

Sources and further reading

  1. ↑ Reinhard Diestel : Graph theory . 4th edition. Springer, 2010, ISBN 978-3-642-14911-5 , pp. 14 .
  2. ↑ Christoph Meinel, Martin Mundhenk: Mathematical foundations of computer science . 3. Edition. Teubner, 2006, ISBN 3-8351-0049-1 .
  3. ↑ Volker Turau: Algorithmic Graph Theory . 2nd Edition. Oldenbourg, 2004, ISBN 3-486-20038-0 .
  4. ^ A b Arthur Cayley (1857): On the Theory of Analytical Forms called Trees. In: Philosophical Magazine, Volume 13, pp. 172–176 (Reprint in: The Collected Mathematical Papers of Arthur Cayley. Volume 3, Cambridge University Press, Cambridge, 1890, pp. 242–246; digitized at the Internet Archive ).
  5. ^ A b Arthur Cayley (1859): On the Theory of Analytical Forms called Trees. Second Part. In: Philosophical Magazine, Volume 17, pp. 374-378. (Reprint in: The Collected Mathematical Papers of Arthur Cayley. Volume 4, Cambridge University Press, Cambridge, 1891, pages 112-115; digitized at the Internet Archive ).

Web links

Wiktionary: sheet  - explanations of meanings, word origins, synonyms, translations