Trees

• Special types of graphs. Important enough to have an entire chapter
• Definition
• Theorem 1
• Rooted tree: We can arbitrarily designate any vertex as root and build a rooted tree.
• For rooted tree we can define ancestor, descendant, child, parent, sibling relations page 534
• internal vertices and leaves
• subtree rooted at a vertex is a subgraph containing all of its descendants and all the edges incident with the descendants
• Def. 2=> m-ary tree means maximum degree of all the vertices is m+1
• full m-ary tree all the internal vertices except root have a degree of m+1. Root's degree is m and leaves have 1 as their degree.
• ordered trees. Order of the children from left to right is important
• Balanced tree
• Theorem 2:
• Theorem 3 and 4 are essentially similar. Minor algebraic manipulations are required to prove one from the other.
• Theorem 5 proved inductively
• Problem 20:
  • lower bound will correspond to balanced tree
  • Use corollary 1
  • Upper bound construct a tree which has one internal vertex at each level
    • for levels1 it 3 it will have m-1 leaves
    • for level 0, 0 leaves
    • for level 4, m leaves

Applications (Section 8.2)

• Binary search tree
  • at the most two children per vertex
  • left child and right child are distinguished from each other (ordered rooted tree)
  • left sub tree and right sub tree
  • All the elements in left subtree are smaller than the root, all the elements in the right subtree are larger than the root
  • left and right sub trees are binary search trees
  • Searching through the binary tree requires traversing a path from root to one of the nodes. Maximum length is equal to the height of the tree
  • See the algorithm from the book
    • If item looking for is in the root, done
    • else if the item is smaller search in the left subtree
    • else search in the right subtree
• Decision trees
• Lays down the decision process
• Figure 3:
  • Shows how you can use two comparisons to find out a light counterfeit coin from 8 coins
  • We have just have to follow a path depending on the outcome of the results of balancing to get to our answer
  • Problem no. 8: more complicated - the counterfeit can be heavier or lighter
  • Show that can't be done with two weighings
    • If we weigh group of 1 or 2, we will be left with more than 3 coins if the groups balance. Definitely will need more than two weighings to go on from there
    • If we weigh groups of three coins, if they don't balance, we are left with a group of six coins that may have a counterfeit.
  • Give an algorithm for three weighings
• Prefix codes
  • 26 characters can be coded with 5 bits per character
  • We can compress this by reducing the number of bits transmitted for high freq characters
  • Say code for e will be a signle bit 0
  • This means different characters will have different length. Can be confusing.
  • Prefix code makes sure that code of one character cannot be starting string of any other code
  • can be obtained using a tree. Write down the code for e, a, n, s, t in figure 4 on page 552.

Spanning Trees

• Definition
• Theorem 1.
• problem #10
  • deleting an edge from the simple circuit will give you a different tree

Minimal Spanning Trees

• Edges may have certain weight: such graphs are called weighted graphs
• From all possible spanning trees, pick the ones that have minimum sum of weights
• Local greedy
  • Solve the problem based on local information, without worrying about global implications
• Prim's algorithm and its proof
• Kruskal's algorithm: easier to prove

Shortest path between two points

• Dijkstra's algorithm
• Exercise number 4 for the asignment.