9780023606922, Chapter 2 6, Problem 7E

Prévia do material em texto

Chapter 2.6, Problem 7E Step-by-step solution Step 1 of 1 Level of Each Vertex in 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 4 9 5 7 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.