CHAP. 9] DIRECTED GRAPHS 205
Fig. 9-2a (directed) path fromvtou. In particular, we say thatvimmediately follows uif(u,v)is an edge, that is, ifv
followsuandvis adjacent tou. We note that every vertexv, other than the root, immediately follows a unique
vertex, but thatvcan be immediately followed by more than one vertex. For example, in Fig. 9-2(a), the vertexj
follows c but immediately followsg. Also, bothiandjimmediately followg.
A rooted treeTis also a useful device to enumerate all the logical possibilities of a sequence of events where
each event can occur in a finite number of ways. This is illustrated in the following example.
EXAMPLE 9.5 Suppose Marc and Erik are playing a tennis tournament such that the first person to win two
games in a row or who wins a total of three games wins the tournament. Find the number of ways the tournament
can proceed.
The rooted tree in Fig. 9-2(b) shows the various ways that the tournament could proceed. There are 10 leaves
which correspond to the 10 ways that the tournament can occur:
MM,MEMM,MEMEM,MEMEE,MEE,EMM,EMEMM,EMEME,EMEE,EESpecifically, the path from the root to the leaf describes who won which games in the particular tournament.
Ordered Rooted Trees
Consider a rooted treeTin which the edges leaving each vertex are ordered. Then we have the concept
of anordered rooted tree. One can systematically label (oraddress) the vertices of such a tree as follows: We
first assign 0 to the rootr. We next assign 1, 2 , 3 ,...to the vertices immediately followingraccording as the
edges were ordered. We then label the remaining vertices in the following way. Ifais the label of a vertexv,
thena. 1 ,a. 2 ,...are assigned to the vertices immediately followingvaccordingas the edges were ordered. We
illustratethis address system in Fig. 9-3(a), where edges are pictured from left to right according to their order.
Observe that the number of decimal points in any label is one less than the level of the vertex. We will refer to
this labeling system as theuniversal address systemfor an ordered rooted tree.
The universal address system gives us an important way of linearly describing (or storing) an ordered rooted
tree. Specifically, given addressesaandb,weleta<bifb=a.c, (that is,ais aninitial segmentofb), or if
there exist positive integersmandnwithm<nsuch that
a=r.m.s and b=r.n.tThis order is called thelexicographic ordersince it is similar to the way words are arranged in a dictionary. For
example, the addresses in Fig. 9-3(a) are linearly ordered as pictured in Fig. 9-3(b). This lexicographic order is