9780023606922, Chapter 2 6, Problem 16E

Prévia do material em texto

Chapter 2.6, Problem 16E Step-by-step solution Step of 6 Children of root, 5: Consider the following rooted tree: 5 (root) 2 7 4 6 9 1 3 8 10 The root of the above tree is Consider the children of 5 Step 2 of 6 We know that, Tree: If V and W are vertices of a simple graph T and there is a unique simple path that is there are no repeated vertices from V and W, then T is a tree. Also a tree is an acyclic graph. Step 3 of 6 Rooted Tree: A Rooted tree is a tree in which a particular vertex is designated as root so that all other vertices are placed under that vertex. Children of a vertex: If T is a tree with root and there is a simple path in T. Then the children of is Step 4 of 6 Now, for example, consider the following tree. Here a is the root the tree. The children of a vertex are all the vertices which have the unique simple path between that vertex and the next level vertex which are as follows: d b (d,e), a (b,c) Step 5 of 6 The example tree is as follows: a b d e Step 6 of 6 Similarly, in the following tree, consider the children of vertex 5:- 5 (root) 2 7 4 6 9 3 8 10 Hence, the children of 5 are 2. 6 and