9780023606922, Chapter 2 6, Problem 9E

Prévia do material em texto

Chapter 2.6, Problem 9E Step-by-step solution Step 1 of 1 Rooted Tree Tree: If V and W are two vertices in a simple graph T and there exists only one simple path between V and W (inclusive) including all vertices without repetition and also including all edges without repetition, then T is said to be a tree. Rooted Tree: A tree which is considered with a specific vertex as its root and all other vertices are places under that vertex is called a rooted tree. Consider the following tree rooted at the vertex 2 9 Root 4 10 1 11 5 8 3 6 7 The rooted tree with vertex 1 as its root is as below: 1 11 2 4 3 5 9 7 10 8 Level of a Vertex: The length of a simple path from the root of the tree to a specific vertex is called the level of that vertex. The level of the root is 0; the level of the vertices under the root is 1, and so on. Height of a Tree: The maximum level of a tree or the number of edges from the root and one of the vertices at the maximum level is called the height of the tree. From the definitions, Level of the vertex 1 is since it is the root of the tree. Level of the vertex 11 is 1 as the length of the simple path from the root 1 to them is 1. Level of the vertices 2, 4, and 3 is 2. Level of the vertices 5 and 9 is 3. Level of the vertices 6, 7, 10 is 4. Level of the vertex 8 is 5. The maximum level of the tree or the number of edges between the farthest vertex 8 and the root 1 is 5. Hence, the height of the tree is 5.