Theory and Application of Graphs
==========================================================================
Chapter 2
Trees
and Graphic Spaces
In this chapter, we will discuss a class of the
simplest connected graphs without cycles, that is, trees, called by almost all authors. Trees will play an important role in
studying structural properties and applications of graphs.
We will first present some basic properties of trees and spanning trees, then discuss relationship between spanning trees and cycles
as well as between cotrees and bonds of a graph. The relations between the set of cycles and the set of bonds of a graph will be further explored with the aid of linear algebraic theory by
establishing the graphic spaces. We are particularly interested in the edge-space of a digraph
G as well as its two subspaces, the
cycle-space and the bond-space, consisting of all cycle-vectors and bond-vectors in the edge-space, respectively. With aid of the
incidence matrix of G we will show that these two subspaces are orthogonally complementary in the edge-space of
G. By a spanning
tree in G, we can easily find the basic matrices of the cycle-space and the bond-space. In view of importance of spanning
trees and as an application of the edge-space theory, we will deduce several formulae for counting the number of spanning in a connected graph without loops.
As applications of spanning trees, we will present two efficient algorithms to solve the minimum connector problem and the shortest
path problem, that is, to find a minimum spanning tree and an optimal spanning tree rooted at a given vertex of a weighted graph, respectively. At the end of this chapter, we will present
an application of the edge-space theory in the electrical network theory.
|
