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
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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

mersin escort adana escort izmir escort gaziantep escort