 |
|
| ||||||||||||||||||||||||||
|
|
| ||||||||||||||||||||||||||
|
|
|
|
|
| ||||||||
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).
A tree is an undirected simple graph G that satisfies any of the following equivalent conditions:
If G has finitely many vertices, say n of them, then the above statements are also equivalent to:
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 and every edge is directed away from it. If each internal vertex has no more than n children, the rooted tree can be called a n-ary tree. If each internal vertex has exactly n children, the rooted tree can be called a full n-ary tree. For n = 2, a tree is called a binary tree.
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.
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 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
See List of graph theory topics: Trees.
|
||||
| View Live Article | This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License | |
||
