|
A Tree is a connected linear graph without any circuit. The concept of a
tree is the most important in the graph theory, especially for applications of graphs.
A linear graph G = (V, E) consists of a
set of objects V =
{v1, v2, v3,...} called vertices and another set e = {e1, e2, e3,...}
called edges, such that each edge ek is identified with an unordered pair
(vi, vj) of
vertices. A tree is a simple graph that has
neither a self-loop nor parallel edges. Tree appears in numerous instances.
The genealogy of a family is often represented by means of a tree. In fact, the term
`Tree' comes from family tree. In many sorting problems one has only two
alternatives at each intermediate vertex,
representing a dichotomy, such as large or small,
good or bad, 0 or 1. Such a decision tree with two choices at each vertex
occurs frequently in computer programming and switching theory.
The concept of tree appeared implicitly in the work of Gustav Kirchhoff
(1824- 1887), who employed graph theoretical ideas in the calculation of current
in electrical networks or circuits (Deo, 1974). The enumeration techniques
involving trees first arose in connection with a problem in differential calculus, but
they were soon extended to the fundamental tools in the counting
of chemical molecules, and now provide a
fascinating topic of interest in their own right.
Cayley was led by the study of the particular analytical forms arising from
differential calculus to study a particular type
of graph, the `tree'. This study has many implications in theoretical chemistry.
It involved techniques mainly concerned with the enumeration of graphs
having particular properties. Cayley (1821-1895), James J Sylvester (1806-1897),
George Polya (1887-1995) and others used trees to enumerate chemical molecules.
Recently, a wide variety of new results in combinatorial enumeration have
been obtained. Many of these results were prompted by new problems in
computer science, while others answered old questions in combinatorics and
other fields. This paper aims to survey history on graph theory and a subset of the
new results—those dealing with tree enumeration.
In method (i), all graphs are counted for labeled
graphs, and each set of isomorphic graphs is
counted as one for unlabeled graphs. For example, let us consider
the enumeration of simple graphs of n vertices and e edges. The number of edges of a completely connected graph is n(n - l)/2 = E, and the number of
edges required to represent any tree of n vertices is
(n - 1) = E (Rakshit et al., 1981). Therefore, the number of distinguishable combinations
of E edges considering e sets of edges are ECe. Hence, the number of distinct trees in
a graph of n vertices and e edges is ECe. Counting specific types of graphs: |
