| Tree (graph Theory) |
Article Index for Tree |
Website Links For Tree |
Information AboutTree (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). A tree may sometimes be referred to as a ''free tree''. DEFINITIONS 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 any of the following conditions:
An undirected simple graph ''G'' is called a ''forest'' if it has no simple cycles. 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. 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}. A ''regular'' (or ''homogeneous'') tree is a tree in which every vertex has the same Degree . See Regular_graph . An ''irreducible'' (or ''series-reduced'') tree is a tree in which there is no vertex of degree 2. 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 ''n''''n''−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 ''d''1,''d''2,...,''d''n 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 : However, some research has been done in this area by Concorde-Carlisle High School, and equations for certain levels of categorization have been obtained. TYPES OF TREES ''See .'' SEE ALSO REFERENCES Concorde-Carlisle High School's Research |
|
|