A labeled tree is one wherein the vertices are labeled. If the tree has n vertices, then {1, 2, 3,..., n} is used as the set of labels. We find that two trees that are isomorphic without labels may become nonisomorphic when labeled. In Fig. 12.8, the first two trees are isomorphic as labeled trees. The third tree is isomorphic to the other two if we ignore the labels; as a labeled tree, however, it is not isomorphic to either of the other two.

The number of nonisomorphic trees with n labeled vertices can be counted by setting up a one-to-one correspondence between these trees and the nn-2 sequences (with repetitions allowed) x1, x2, . . ., xn-2 whose entries are taken from {1, 2, 3,..., n} If r is one such labeled tree, we use the following algorithm to find its corresponding sequence - called the Prufer code for the tree. (Here T has at least one edge.)
Step 1: Set the counter i to 1.
Step 2: Set T(i) = T.
Step 3: Since a tree has at least two pendant vertices, select the pendant vertex in T (i) with the smallest label yt. Now remove the edge {xl, yl} from T(i) and use xl for the ith component of the sequence.
Step 4: If i = n - 2, we have the sequence corresponding to the given labeled tree T(1). If i ‰  n - 2, increase i by 1, set T(i) equal to the resulting subtree obtained in step (3), and return to step (3).
(a) Find the six-digit sequence (Prufer code) for trees (i) and (iii) in Fig. 12.8.
(b) If v is a vertex in T, show that the number of times the label on v appears in the Prufer code x1, x2, ..., xn-2 is deg(n) - 1.
(c) Reconstruct the labeled tree on eight vertices that is associated with the Prufer code 2, 6, 5, 5, 5, 5.
(d) Develop an algorithm for reconstructing a tree from a given Prufer code x1, x2,..., xn-2.

Transcribed Image Text:

4 4 1 1 4 (iii)