Question

List the vertices of the ordered rooted trees in Figures 3 and 9 of Section 11.3 in level order.

Short answer

Therefore, the list of vertices of the ordered rooted trees in Figures 3 and 9 of Section 11.3 in level order is\({\bf{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}}\) and \({\bf{a,b,c,d,e,f,g,h,i,j,k}}\).

Step-by-step solution

General form

Definition of tree: A tree isa connected undirected graph with no simple circuits.

Definition of Circuit: It is a path that begins and ends in the same vertex.

Definition of rooted tree: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

Level order (Definition): The listing of the vertices of an ordered rooted tree in level order begins with the root, followed by the vertices at level 1 from left to right, followed by the vertices at level 2 from left to right, and so on.

Evaluate the level order of the trees

Given that, the ordered rooted trees.

Referring Section 11.3: Figure 3 and 9 are shown below.

Figure 3:

Figure 9:

Now, let us find the level order of an ordered trees, the listing of the vertices starting with the root, then the vertices at level 1 from left to right, then vertices at level2 from left to right, and so on.

Level order of Figure 3: \({\bf{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p}}\).

Level order of Figure 9: \({\bf{a,b,c,d,e,f,g,h,i,j,k}}\).

Conclusion: The founded graphs are representing the level order of the vertices.