Tree (graph theory)

related topics
{math, number, function}
{specie, animal, plant}
{woman, child, man}
{line, north, south}

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree. A forest is a disjoint union of trees.

The various kinds of data structures referred to as trees in computer science are similar to trees in graph theory, except that computer science trees have directed edges. Although they do not meet the definition given here, these graphs are referred to in graph theory as ordered directed trees (see below).

Contents

Definitions

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

  • G is connected and has no cycles.
  • G has no 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 K3 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 irreducible (or series-reduced) tree is a tree in which there is no vertex of degree 2.

A forest is an undirected graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees. Equivalently, a forest is an undirected cycle-free graph. As special cases, an empty graph, a single tree, and the discrete graph on a set of vertices (that is, the graph with these vertices that has no edges), all are examples of forests.

The term hedge sometimes refers to an ordered sequence of trees.

A polytree or oriented tree is a directed graph with at most one undirected path between any two vertices. In other words, a polytree is a directed acyclic graph for which there are no undirected cycles either.

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 (see arborescence).

Full article ▸

related documents
Nial
Coprime
Consistency
Referential transparency (computer science)
Real analysis
Quotient group
P-complete
Lagrange inversion theorem
Hahn–Banach theorem
Epimorphism
Chomsky hierarchy
Statistical independence
Codomain
Associativity
Dual number
Local field
Elementary group theory
Mathematical singularity
Zorn's lemma
Examples of groups
Functional analysis
Legendre symbol
Arithmetic shift
Axiom of pairing
Linear cryptanalysis
Extended Backus–Naur Form
Group isomorphism
Venn diagram
Unicity distance
Haar measure