370 CHAPTER 6 Graph Theory
- Find a tracing that minimizes the number of pen lifts for the graph shown.
12 13 14
NA L 111 TO 9- Prove that any Eulerian graph can be decomposed into a set of pairwise edge-disjoint
cycles.
rnTrees
Historically, the study of trees was independently initiated by Arthur Cayley (1821-1895
b. England) and Gustav Kirchoff (1824-1887, b. Prussia). Cayley's work in the 1850s
used these graphs as a tool for counting the number of saturated hydrocarbons C, H2n+ 2
containing n carbon atoms and 2n + 2 hydrogen atoms. Kirchoff's work in 1847 used
this same family of graphs to solve a system of simultaneous linear equations that give
the current in each branch and around each circuit of an electrical network. Figure 6.33, on
page 371, shows examples of typical graphs representing the problems Cayley and Kirchoff
dealt with.
In Cayley's work, trees are used to represent the structure of hydrocarbons. Hydro-
carbons contain atoms of hydrogen, oxygen, carbon, and nitrogen. The letters in Figure
6.33(a) represent the atoms, and a line between a pair of atoms represents a chemical bond.
Methane, for example, is composed of four hydrogen atoms that are bonded to one car-
bon atom. Atoms of hydrogen always correspond to vertices of degree 1; atoms of carbon
always correspond to vertices of degree #1.
In Figure 6.33(b), the top figure represents an electrical network with resistances,
condensers, and inductances. This information was replaced with the graph G. Kirchoff
showed that it was not necessary to consider every cycle in the associated graph of an elec-
trical network separately to solve the system of equations in which he was interested. He
showed that all the needed information was contained in any tree, such as T.
In more recent applications, trees are used to solve problems regarding the most ef-
ficient way to link a number of locations, whether by roads or by computer networks. In
computer science, trees are used to represent hierarchical structures, such as file systems,
as well as arithmetic expressions.
This section provides several different characterizations of trees. In Section 6.11, at-
tention will focus on the problem of finding a "smallest" connected spanning subgraph in
a graph. After solving this problem, we will focus in Section 6.12 on rooted trees and the
application of these trees to sorting and searching. We will show how trees can provide a
model for determining a lower bound on the complexity of any sorting algorithm that is
based on the comparison of two elements at a time.