Tree (graph theory)

A tree is a connected acyclic graph. [1] Connectivity means the presence of paths between any pair of vertices, acyclicity — the absence of cycles, and the fact that there is only one path between pairs of vertices.

A forest is an ordered set of ordered trees.

Oriented (directed) tree is an acyclic digraph (a directed graph that does not contain cycles), in which only one vertex has zero degree of entry (no arcs lead to it), and all other vertices have degree of entry 1 (they lead along exactly one arc ). A node with a zero degree of entry is called the root of a tree, and peaks with a zero degree of outcome (from which no arc comes) are called terminal vertices or leaves . [2]

The root tree is a tree in which one vertex is selected (the root of the tree). Formally, the root tree is defined as a finite set one or more nodes with the following properties:

1. there is one root of a tree
2. the remaining nodes (with the exception of the root) are distributed among disjoint sets , and each of the sets is a root tree; trees are called subtrees of this root

Related definitions

• The node degree is the number of outgoing arcs (or, otherwise, the number of node subtrees).
• A leaf node ( leaf , terminal vertex ) is a node with degree 1 (that is, a node into which only one edge leads; in the case of an oriented tree, a node into which only one arc leads and not a single arc goes).
• The branch node is a non-leaf node.
• Node level - path length from root to node. You can define recursively:

1. tree root level equals 0;
2. the level of any other node is one greater than the root level of the nearest subtree of the tree containing this node.

• A tree with a marked top is called a root tree .
  • tier wood - many tree nodes, at the level from the root of the tree.
  • partial order on vertices: if vertices and different and top lies on the (unique!) elementary chain connecting the root to the vertex .
  • root subtree with root - subgraph .
  • In a context where a tree is supposed to have a root, a tree without a selected root is called free .
• A spanning tree (s) is a subgraph of a given graph containing all its vertices and is a tree. The edges of the graph, not included in the core, are called chords of the graph with respect to the core.
• An irreducible tree is a tree in which there are no vertices of degree 2.
• A forest is a set (usually ordered) that does not contain a single non-intersecting tree or contains several non-intersecting trees.

Binary tree

A simple binary tree of size 9 and height 3, with a root of value 2. This tree is not balanced and not sorted.

The term binary tree (it is also a binary tree ) has several meanings:

• A non-oriented tree in which the degrees of the vertices do not exceed 3.
• An oriented tree in which the outgoing degrees of the vertices (the number of outgoing edges) do not exceed 2.
• Abstract data structure used in programming. Data structures such as a binary search tree, binary heap, red-ebony, AVL-tree, Fibonacci heap, etc. are based on a binary tree.

N-ary trees

N-ary trees are defined by analogy with a binary tree. For them, there are also oriented and non-oriented cases, as well as corresponding abstract data structures.

• An N-ary tree (non-oriented) is a tree (normal, non-oriented) in which the degrees of the vertices do not exceed N + 1.
• An N-ary tree (oriented) is an oriented tree in which the outgoing degrees of the vertices (the number of outgoing edges) do not exceed N.

Properties [edit]

• The tree has no multiple edges and loops.
• Any tree with vertices contains edge. Moreover, a finite connected graph is a tree if and only if where - the number of vertices - the number of edges of the graph.
• A graph is a tree if and only if any two different vertices of it can be connected by a single simple chain.
• Any tree is uniquely determined by the distances (the length of the smallest chain) between its terminal (degree 1) vertices.
• Any tree is a bichromatic graph. Any tree whose vertex set is at most countable is a planar graph.
• For any three vertices of the tree, the paths between the pairs of these vertices have exactly one common vertex.

Tree Counting

Main article: Cayley's theorem on the number of trees

• The number of different trees that can be built on numbered vertices equal to ( Cayley's theorem [3] ).
• Generating function

for the number nonisomorphic rooted trees with vertices satisfies the functional equation

.

• Generating function

for the number non-isomorphic trees with vertices can be represented using the enumeration series for root trees:

• With the following asymptotics is true

Where and certain constants , .

Tree coding

The tree can be encoded with sets of zeros and ones. Consider, for example, laying wood on a plane. Starting from any vertex, we move along the edges of the tree, turning at each vertex to the nearest edge to the right and turning back at the terminal vertices of the tree. Passing along some edge, we write when moving along the edge for the first time and when moving along the edge a second time (in the opposite direction). If a - the number of edges of the tree, then through steps we will return to the original vertex, passing along each edge twice. The resulting sequence from and (tree code) length allows you to uniquely recover not only the tree itself but its laying on the plane. Arbitrary tree correspond to several such codes. In particular, the following rough estimate for the number of trees with tops: