Tree (graph theory): Difference between revisions
→Facts: Countable trees are planar graphs. |
m →Facts: Word "graph" was missing. |
||
Line 28: | Line 28: | ||
== Facts == |
== Facts == |
||
Every tree is a [[bipartite graph|bipartite]] graph. Every tree with only [[Countable set|countably]] many vertices is a [[planar graph |
Every tree is a [[bipartite graph|bipartite]] graph. Every tree with only [[Countable set|countably]] many vertices is a [[planar graph]]. |
||
Every connected graph ''G'' admits a [[spanning tree (mathematics)|spanning tree]], which is a tree that contains every vertex of ''G'' and whose edges are edges of ''G''. |
Every connected graph ''G'' admits a [[spanning tree (mathematics)|spanning tree]], which is a tree that contains every vertex of ''G'' and whose edges are edges of ''G''. |
Revision as of 20:03, 13 July 2005
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 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.
Given n labeled vertices, there are nn−2 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 d1,d2,...,dn is
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
Types of trees
See List of graph theory topics: Trees.