Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 9] DIRECTED GRAPHS 223

(a) List the vertices while proceeding fromRdown the tree to the vertex. The number of vertices, other thanR,isthe

level number:

(i)α=(R,A,C,H), n= 3 ; (ii)α=(R, B, F ), n= 2 ; (iii)α=(R,B,G,L,M), n= 4.

(b) The siblings ofEareFandGsince they all have the same parentB.

(c) The leaves are vertices with no children, that is,H,D,I,J,K,M,N.

Fig. 9-22

9.6. LetTbe the ordered rooted tree in Fig. 9-23 whose vertices are labeled using the universal address system.
Find the lexicographic order of the addresses of the treeT.
An ordered rooted treeTis usually drawn so the edges are ordered from left to right as in Fig. 9-23. The lexicographic
order can be obtained by reading down the leftmost branch, then the second branch from the left, and so forth.
Reading down the leftmost branch ofTwe obtain:

0 , 1 , 1. 1 , 1. 1. 1

The next branch is 1.2, 1.2.1, 1.2.1.1, so we add this branch to the list to obtain

0 , 1 , 1. 1 , 1. 1. 1 , 1. 21. 2. 1 , 1. 2. 1. 1

Proceeding in this manner, we finally obtain

0 , 1 , 1. 1 , 1. 1. 1 , 1. 2 , 1. 2. 1 , 1. 2. 1. 1 , 1. 2. 2 , 1. 3 , 2 , 2. 1 , 2. 2. 1

Fig. 9-23

SEQUENTIAL REPRESENTATION OF GRAPHS

9.7. Consider the graphGin Fig. 9-21(a), and suppose the vertices are stored in memery in the array:

DATA:X, Y, Z, W