3.1 Denition: A tree is a connected graph with no circuits. Theorem 1: Let T be a connected graph. The following are equivalent: (a) T has no circuits. (b) Let a be a node in T . nodes x, a unique path between a and x. (c) nodes x, y a unique path between x and y. (d) T is minimally connected: T \\ e is not connected for every edge e. Theorem 2: A tree on n nodes has n 1 edges. Def: A leaf is a node in a rooted tree with no children. Def: An internal node is a node in a rooted tree that is not a leaf. Def: An m-ary tree is a tree in which each internal node has m children. Theorem 3: An m-ary tree with i internal nodes has n = mi + 1 nodes. Cor: An m-ary tree T : (a) i internal nodes imply l = (m 1)i + 1 leaves. (b) l leaves imply i = (l 1)/(m 1) internal nodes and n = (ml 1)/(m 1) nodes. (c) n nodes imply i = (n 1)/m internal nodes and l = ((m 1)n + 1)/m leaves. Def: The height of a tree is the length of the longest path from the root to a leaf. Def: A rooted tree is balanced if all leaves are at level h or h 1. Theorem 4: Let T be an m-ary tree of height h with l leaves. (a) l mh . (b) h logm l , and if the tree is balanced h = logm l Example 4: Given n coins, one of which is fake, lighter than the others. We are given a balance that can compare 2 sets of coins. How many weighings are needed to nd the fake coin? Section 3.2: Searching a graph At the start, no nodes have been \"seen\". s a given start node. \"list\" nodes that have been seen but not yet explored. Search Algorithm put s on list. mark s as \"seen\". while list is not empty Pick a node i list. If edge (i, j) j unseen then do: Mark j as \"seen\" Mark edge (i, j) as tree edge put j on list Otherwise remove i from list. End. Think: Why do we get a search \"tree\"?? pick LIFO=DFS or FIFO=BFS. Applications: Example 1: Checking if a graph is connected Example 2: Maze searching Example 3: Pitcher pouring puzzle: Given 3 pitchers of sizes 10, 7,4 quarts, initially the 10 is full, others are empty. We can pour from one pitcher to another until either the receiving pitcher is full or the pouring pitcher is empty (whichever comes rst). Pour to obtain exactly 2 quarts in the 4 or 7 quart pitcher. Example 4: Missionaries-Cannibals puzzle: Given 3 missionaries and 3 cannibals that must cross a river in a 2 person boat, how can this be done so that at no time do the missionaries outnumber the cannibals on either side (unless the number of missionaries is zero). Exc 25: 4 people must crosee a bridge, at most 2 at a time, using a single ashlight. Person A takes 1 minute to cross, Person B 2 minutes, Person C 5 minutes and Person D 10 minutes. Two people travelling together go at the slower speed. How can all 4 get across in 17 minutes