Discrete Mathematics for Computer Science

380 CHAPTER 6 Graph Theory

parent-child

ancestor

siblings

Descendantt,

Figure 6.40 Relationships between vertices.

In discussing graphs, the notion of a subgraph clarified what is meant by a substruc-

ture. In the case of a rooted tree, a rooted subtree is the analogue. To define a rooted

subtree, let v be a vertex of the rooted tree T. The rooted subtree of T rooted at v is the

induced subgraph of T defined by the vertex set consisting of v together with all its de-

scendants in T. Figure 6.41 shows two subtrees of the rooted tree shown in Figure 6.38. (A

similar notion was introduced with expression trees in Section 2.1.2.)

Residential Network Tech. Support Groups

Engr. Psych. Chem.

Userl User2 ... UserN Labs Labs Labs

Cscil8O Csci203 Elec315

(a) (b)

Figure 6.41 Support area for the computer center. a. Residental network. b. Technical

support groups.

6.12.1 Binary Trees

A vertex in a rooted tree may have any number of children. The children of a vertex in a

rooted tree are not arranged in any order with respect to their parent or with respect to each

other. The two rooted trees in Figure 6.42 are isomorphic rooted trees. In addition to the

usual properties of an isomorphism between two graphs, an isomorphism between rooted

trees must map the root of one tree to the root of the other.

a a

b eZ c b

d d

Figure 6.42 Two isomorphic rooted trees.