Chapter 11: Trees

Which connected simple graphs have exactly one spanning tree?

Suppose that in a long bit string the frequency of occurrence of a 0 bit is 0.9 and the frequency of a 1 bit is 0.1 and bits occur independently.

a. Construct a Huffman code for the four blocks of two bits, 00, 01, 10, and 11. What is the average number of bits required to encode a bit string using this code?

b.Construct a Huffman code for the eight blocks of three bits. What is the average number of bits required to encode a bit string using this code?

Use Prim's algorithm to find a minimum spanning tree for the given weighted graph.

Answer these questions about the rooted tree illustrated.

1. Which vertex is the root\(?\)
2. Which vertices are internal\(?\)
3. Which vertices are leaves\(?\)
4. Which vertices are children of \({\bf{j}}\)\(?\)
5. Which vertex is the parent of \({\bf{h}}\)\(?\)
6. Which vertices are siblings of \({\bf{o}}\)\(?\)
7. Which vertices are ancestors of \({\bf{m}}\)\(?\)
8. Which vertices are descendants of \({\bf{b}}\)\(?\)

In Exercises 2–6 find a spanning tree for the graph shown by removing edges in simple circuits.

How many comparisons are needed to locate or to addeach of these wordsin the search tree for Exercise 1, starting fresh each time?

a) pear

b) banana

c) kumquat

d) orange

In Exercises 1 – 3 construct the universal address system for the given ordered rooted tree. Then use this to order its vertices using the lexicographic order of their labels.

Give at least three examples of how trees are used in modeling.

Show that every tree with at least one edge must have at least two pendant vertices.

Show that if a game of nim begins with two piles containing different numbers of stones, the first player wins when both players follow optimal strategies.