Trees

History and General Definition

The concept of a tree started with pioneering works of Gustav Kirchhoff (1824-1887), in which the idea of graph-theory has been applied in the calculation of currents in electrical networks. After that, trees have been applied by Cayley (1857), Sylvester (1877), Polya and Read (1987), Wilson (2002) and others. The concepts of the center/bi-center and centroid/bi-centroid of a tree were independently defined by Sylvester (1877). Cayley (1889) found a method for solving the more difficult problem of counting un-rooted trees. In a fundamental paper, Polya and Read (1987) combined the traditional idea of a generation function with that of a permutation to obtain a robust theorem which enabled them to enumerate certain types of configuration under the action of symmetry groups. Later results on the enumeration of trees were obtained by Otter (1948) and others. Subsequently, the graphical enumeration field was further developed by Harary and Palmer (1973), Read (1963) and others. The graphic notation of Crum Brown explained for the first time the phenomenon of isomerism, whereby there exist pairs of molecules (isomers) with the same chemical formula but different chemical attributes. Sylvester (1878) conducted thorough studies on the graphic approach to chemical molecules and invariant theory.

It must be mentioned that an acyclic graph is one that contains no cycles. An acyclic graph is named forest. Each component of an acyclic graph is a tree. Thus, a tree is a good name for a connected acyclic graph. The trees on six vertices are shown in Figure 1. This figure also shows a forest with two components, each of which is a tree. It must be noted that trees and forests are simple graphs.

Figure 1.

Trees on six vertices