Encyclopedia > Tree (graph theory)

  Article Content

Tree (graph theory)

In graph theory, a tree is a graph in which, roughly speaking, any two vertices are connected by a single path.

Table of contents

Definitions

An undirected simple graph G is called 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

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

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

Types of Trees

See also Tree structure.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Westhampton Beach, New York

... total area is 2.35% water. Demographics As of the census of 2000, there are 1,902 people, 805 households, and 498 families residing in the village. The populatio ...

 
 
 
This page was created in 25.2 ms