TREE (GRAPH THEORY)

In graph theory, a 'tree' is a graph in which any two vertices are connected by ''exactly one'' path. Alternatively, any connected graph with no cycles is a tree. A 'forest' is a disjoint union of trees. Trees are widely used in computer science data structures such as binary search trees, heaps, tries, etc.

Contents

Definitions

Example

Facts

Enumeration

Types of trees

See also

References

Definitions

A 'tree' is an undirected simple graph ''G'' that satisfies any of the following equivalent conditions:

★ ''G'' is connected and has no simple cycles.

★ ''G'' has no simple cycles, and a simple cycle is formed if any edge is added to ''G''.

★ ''G'' is connected, and it is not connected anymore if any edge is removed from ''G''.

★ ''G'' is connected and the 3-vertex complete graph $K\_3$ is not a minor of ''G''.

★ Any two vertices in ''G'' can be connected by a unique simple path.
If ''G'' has finitely many vertices, say ''n'' of them, then the above statements are also equivalent to any of the following conditions:

★ ''G'' is connected and has ''n'' − 1 edges.

★ ''G'' has no simple cycles and has ''n'' − 1 edges.
An undirected simple graph ''G'' is called a ''forest'' if it has no simple cycles.
A 'directed tree' is a directed graph which would be a tree if the directions on the edges were ignored. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex.
A ''tree'' is called a 'rooted tree' if one vertex has been designated the ''root'', in which case the edges have a natural orientation, ''towards'' or ''away'' from the root. Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure. A tree without any designated root is called a 'free tree'.
A 'polytree' has at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph (DAG) for which there are no undirected cycles either.
A 'labeled tree' is a tree in which each vertex is given a unique label. The vertices of a labeled tree on ''n'' vertices are typically given the labels 1, 2, …, ''n''.
A ''regular'' (or ''homogeneous'') tree is a tree in which every vertex has the same degree. See regular graph.
An ''irreducible'' (or ''series-reduced'') tree is a tree in which there is no vertex of degree 2.
An ''ordered tree'' is a tree for which an ordering is specified for the children of each node.

Example

The example tree shown to the right has 6 vertices and 6 − 1 = 5 edges. The unique simple path connecting the vertices 2 and 6 is 2-4-5-6.

Facts

★ Every tree is a bipartite graph. Every tree with only countably many vertices is a planar graph.

★ Every connected graph ''G'' admits a spanning tree, which is a tree that contains every vertex of ''G'' and whose edges are edges of ''G''.

★ Every non-null tree has at least one ''leaf'', or vertex of degree 1 (If it has a vertex, it has a leaf).

Enumeration

Given ''n'' labeled vertices, there are ''n''^''n''−2 different ways to connect them to make a tree. This result is called Cayley's formula. It can be proved by first showing that the number of trees with ''n'' vertices of degree ''d''₁,''d''₂,...,''d''_n is the multinomial coefficient
:$\{n-2\; choose\; d\_1-1,\; d\_2-1,\; ldots,\; d\_n-1\}.$
Counting the number of unlabeled trees is a harder problem. No closed formula for the number ''t''(''n'') of trees with ''n'' vertices up to graph isomorphism is known. proved that
:
with ''C'' = 0.53495… and α = 2.95576… (here, ''f'' ∼ ''g'' means that lim ''f''/''g'' = 1).

Types of trees

''See List of graph theory topics: Trees.''

See also

★ Tree structure

★ Tree data structure

★ Binary tree

References

★ .