## Lecture Eight: Trees, part 1

• Def - a tree is connected graph without circuits

• Textbook quickly switched to rooted trees: trees with distinguished "root" element; we'll look first at general trees without roots..
• Prop - If G = (V,E) is is connected, then V <= E+1

• Prop - If G = (V,E) is a tree, then V = E+1

• Prop - If G = (V,E) is connected, and V = E+1, then G is a tree!

• Prop - Every tree has as least 2 vertices of degree 1.

• Prop - If G = (V,E) is a tree, then there is a unique path between any pair of vertices
• If we designate a vertex to be root, then we get a rooted tree. Can now view as directed, with all arcs going away from root
• We then get notions like "level number" (hops from root); internal node (node with children); leaf (node without children); branching factor (number of children). If this is constant for all internal nodes, and if its value is m, we call the tree m-ary.
• height of tree is highest level number in tree. For m-ary trees, height is logarithmic in # of leaves. This fact makes the world go around in CS.

• Thm: If N = number of vertices, i = number of internal nodes, L = number of leaves, T is m-ary, then N = mi+1, N = i + L, and a whole bunch of other complicated (but easy to prove) results follow, e.g. L = (m-1)i + 1 -- this is all in textbook

-- RobbieMoll - 03 Oct 2006

Topic revision: r1 - 2006-10-03 - RobbieMoll    Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback