9780023606922, Chapter 2 6, Problem 8E

Prévia do material em texto

Chapter 2.6, Problem 8E Step-by-step solution Step 1 of 1 Height of a 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 11 2 9 Root 4 10 1 11 5 8 3 6 7 So, consider the level of each vertex. 11 1 30 4 9 5 10 6 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. Level of the vertex 11 is 0. since it is the root of the tree. Level of the vertices 1. 2. 3 and 4 is 1 as the length of the simple path from the root 11 to them is 1. Level of the vertices 9 and 5 is 2. Level of the vertices 10. 6 and 7 is 3. Level of the vertex 8 is 4. 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. The maximum level of the tree or the number of edges between the farthest vertex 8 and the root 11 is Hence, the height of the tree is 4.