Seyed Abbas Hosseinijou (Amirkabir University of Technology, Iran), Farhad Kiya (Amirkabir University of Technology, Iran) and Hamed Kalantari (University of Science and Technology, Iran)
DOI: 10.4018/978-1-4666-2661-4.ch005
OnDemand PDF Download:
List Price: $37.50


In this chapter, the authors present a special and important type of graphs named Trees. Although the concept of a tree is simple, many applications of graph theory in science and engineering are related to this type. The topics of this chapter are selected based on theory and application of trees. Rooted trees, spanning trees, fundamental cycles and bounds, and tree search algorithms are covered. However, this chapter mainly focuses on spanning trees and tree search algorithms.
Chapter Preview


The idea of a family tree is well known for all of us. In many ways a tree is the simplest non-trivial type of graphs. According to these, trees have several 'nice' attributes, as an example of these properties; any two vertices are connected by a particular path. If we want to try to prove a general result for graphs, it is better to start by trying to prove it for trees. In fact, several conjectures that have not been proved for arbitrary graphs are known to be true for trees. In this chapter, we will study the trees thoroughly and with special references to rooted trees and spanning trees and also to Cayley's celebrated result on the enumeration of labeled trees. Also, the chapter will continue with the concepts of fundamental cycles and bonds and will conclude with tree search algorithms.

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

Complete Chapter List

Search this Book: