Trees • Definition ○ A tree is a connected undirected graph with no simple circuits. • Example ○ Which of these graphs are trees? • Solution ○ G_1 and G_2 are trees - both are connected and have no simple circuits ○ Because e, b, a, d, e is a simple circuit, G_3 is not a tree. ○ G_4 is not a tree because it is not connected. • Definition ○ A forest is a graph that has no simple circuit, but is not connected. ○ Each of the connected components in a forest is a tree. • Theorem ○ An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices. • Proof ○ (⟹)Assume that T is a tree. § Then T is connected with no simple circuits. § Hence, if x and y are distinct vertices of T, there is a simple path between them (by Theorem 1 of Section 10.4). § This path must be unique - for if there were a second path, there would be a simple circuit in T (by Exercise 59 of Section 10.4). § Hence, there is a unique simple path between any two vertices of a tree. ○ (⟸)Now assume that there is a unique simple path between any two vertices of a graph T. § Then T is connected because there is a path between any two of its vertices. § Furthermore, T can have no simple circuits since if there were a simple circuit, there would be two paths between some two vertices. ○ Hence, a graph with a unique simple path between any two vertices is a tree. Rooted Trees • Definition ○ 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. • An unrooted tree is converted into different rooted trees when different vertices are chosen as the root. Rooted Tree Terminology • Terminology for rooted trees is a mix from botany and genealogy (such as this family tree of the Bernoulli family of mathematicians). • If v is a vertex of a rooted tree other than the root, the parent of v is the unique vertex u such that there is a directed edge from u to v. • When u is a parent of v, v is called a child of u. • Vertices with the same parent are called siblings. • The ancestors of a vertex are the vertices in the path from the root to this vertex, excluding the vertex itself and including the root. • The descendants of a vertex v are those vertices that have v as an ancestor. • A vertex of a rooted tree with no children is called a leaf. • Vertices that have children are called internal vertices. • If a is a vertex in a tree, the subtree with a as its root is the subgraph of the tree consisting of a and its descendants and all edges incident to these descendants. Examples of Rooted Trees • Example: In the rooted tree T (with root a): ○ Find the parent of c, the children of g, the siblings of h, the ancestors of e, and the descendants of b. ○ Find all internal vertices and all leaves. ○ What is the subtree rooted at G? • Solution: ○ The parent of c is b. The children of g are h, i, and j. The siblings of h are i and j. The ancestors of e are c, b, and a. The descendants of b are c, d, and e. ○ The internal vertices are a, b, c, g, h, and j. The leaves are d, e, f, i, k, l, and m. ○ We display the subtree rooted at g. Properties of Trees • Theorem 2 ○ A tree with n vertices has n − 1 edges. • Proof (by mathematical induction): ○ Basis Step § When n = 1, a tree with one vertex has no edges. § Hence, the theorem holds when n = 1. ○ Inductive Step § Assume that every tree with k vertices has k − 1 edges. § Suppose that a tree T has k + 1 vertices and that v is a leaf of T. § Let w be the parent of v. § Removing the vertex v and the edge connecting w to v produces a tree T′ with k vertices. § By the inductive hypothesis, T′ has k − 1 edges. § Because T has one more edge than T′, we see that T has k edges. § This completes the inductive step. m-ary Rooted Trees • Definition ○ A rooted tree is called an m-ary tree if every internal vertex has no more than m children. ○ The tree is called a full m-ary tree if every internal vertex has exactly m children. ○ An m-ary tree with m = 2 is called a binary tree. • Example ○ Are the following rooted trees full m-ary trees for some positive integer m? • Solution ○ T_1 is a full binary tree because each of its internal vertices has two children. ○ T_2 is a full 3-ary tree because each of its internal vertices has three children. ○ In T_3 each internal vertex has five children, so T3 is a full 5-ary tree. ○ T_4 is not a full m-ary tree for any m because some of its internal vertices have two children and others have three children. Counting Vertices in Full m-Ary Trees • Theorem 3 ○ A full m-ary tree with i internal vertices has n = mi + 1 vertices. • Proof ○ Every vertex, except the root, is the child of an internal vertex. ○ Because each of the i internal vertices has m children, ○ there are mi vertices in the tree other than the root. ○ Hence, the tree contains n = mi + 1 vertices. • Theorem 4 ○ A full m-ary tree with § n vertices has i=(n−1)/m internal vertices and l=((m−1)n+1)/m leaves, § i internal vertices has n = mi + 1 vertices and l=(m−1)i+1 leaves, § l leaves has n=(ml−1)/(m−1) vertices and i=(l−1)/(m−1) internal vertices. ○ Proof (of part i) § Solving for i in n = mi + 1 (from Theorem 3) gives i=(n−1)/m. § Since each vertex is either a leaf or an internal vertex, n=l+i. § By solving for l and using the formula for i, we see that § l=n−i=n−(n−1)/m=((m−1)n+1)/m Level of vertices and height of trees • When working with trees, we often want to have rooted trees where the subtrees at each vertex contain paths of approximately the same length. • To make this idea precise we need some definitions: ○ The level of a vertex v in a rooted tree is the length of the unique path from the root to this vertex. ○ The height of a rooted tree is the maximum of the levels of the vertices. • Example: ○ Find the level of each vertex in the tree to the right. ○ What is the height of the tree? • Solution: ○ The root a is at level 0. ○ Vertices b, j, and k are at level 1. ○ Vertices c, e, f, and l are at level 2. ○ Vertices d, g, i, m, and n are at level 3. ○ Vertex h is at level 4. ○ The height is 4, since 4 is the largest level of any vertex. Balanced m-Ary Trees • Definition ○ A rooted m-ary tree of height h is balanced if all leaves are at levels h or h − 1. • Example ○ Which of the rooted trees shown below is balanced? • Solution ○ T_1 and T_3 are balanced, but T_2 is not because it has leaves at levels 2, 3, and 4. The Bound for the Number of Leaves in an m-Ary Tree • Theorem 5 ○ There are at most mh leaves in an m-ary tree of height h. • Proof (by mathematical induction on height): ○ Basis Step § Consider an m-ary trees of height 1. § The tree consists of a root and no more than m children, all leaves. § Hence, there are no more than m^1=m leaves in an m-ary tree of height 1. ○ Inductive Step § Assume the result is true for all m-ary trees of height h. § Let T be an m-ary tree of height h. § The leaves of T are the leaves of the subtrees of T we get when we delete the edges from the root to each of the vertices of level 1. § Each of these subtrees has height ≤ h−1. § By the inductive hypothesis, each of these subtrees has at most mh− 1 leaves. § Since there are at most m such subtrees, there are at most m⋅m^(h1) = mh leaves in the tree. • Corollary 1 ○ If an m-ary tree of height h has l leaves, then h ≥ ⌈log_ml⌉. ○ If the m-ary tree is full and balanced, then h = ⌈log_ml⌉. (see text for the proof)
