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
An undirected simple graph G is a tree if it satisfies one (and therefore all) 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.
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 planar and bipartite.
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 different vertices, there are nn-2 different ways to connect them to make a tree. 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
Types of Trees
See also Tree structure, Tree data structure.
Referenced By
Depth-first search | Depth first search | Forest (disambiguation) | List of graph theory topics | List of mathematical topics (S-U) | Phylogenetic tree | Real tree
|
