tree (graph theory)

In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. A forest is a graph in which any two vertices are connected by at most one path. An equivalent definition is that a forest is a disjoint union of trees (hence the name).

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, if any edge is added to G, then a simple cycle is formed
G is connected and, if any edge is removed from G, then it is not connected anymore
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:

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 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 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}.

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 planar and bipartite 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. Given n labeled vertices, there are nⁿ⁻² different ways to connect them to make a tree. This result is called Cayley's formula. The number of trees with n vertices of degree d₁,d₂,...,d_n is

{n-2 \choose d_1-1, d_2-1, \ldots, d_n-1},

which is a multinomial coefficient. No closed formula for the number t(n) of trees with n vertices up to graph isomorphism is known. However, the asymptotic behavior of t(n) is known: there are numbers α ≈ 3 and β ≈ 0.5 such that

\lim_{n\to\infty} \frac{t(n)}{\beta \alpha^n n^{-5/2}} = 1.

Types of trees

See List of graph theory topics: Trees.

<< Previous

Word Browser

Next >>

provence
philosophical movement
terrestrial ecoregion
terrestrial planet
sublette county, wyoming
antelope
oxford university press
highway
sloop
angela davis
eurasian avars

blood vessel
dry ski slope
juan manuel fangio
pennsylvania avenue
telex (band)
charles maurice de talleyrand
bah'
dopamine
organisation of african unity
denver and rio grande western railroad
television licence

irvine welsh
chess variant
archbishop
synagogue
air traffic control
ecovillage
shimon peres
egbert of wessex
ethelwulf of wessex
citeaux abbey
the andromeda strain

a, an
romany
atomic, molecular, and optical physics
artcyclopedia
ethelbald of wessex
pulitzer prize for fiction
ethelbert of wessex
martyr
graph
barbara pym
history of japan