Chapter 11: Trees

Devise an algorithm for constructing a rooted tree from the universal addresses of its leaves.

Express Sollin’s algorithm in pseudo code.

Show that an ordered rooted tree is uniquely determined when a list of vertices generated by a preorder traversal of the tree and the number of children of each vertex are specified.

Use backtracking to try to find a coloring of each of the graphs in Exercises 7–9 of Section 10.8 using three colors.

a) Use Huffman coding to encode these symbols with frequencies \({\bf{a: 0}}{\bf{.4, b: 0}}{\bf{.2, c: 0}}{\bf{.2, d: 0}}{\bf{.1, e: 0}}{\bf{.1}}\) in two different ways by breaking ties in the algorithm differently. First, among the trees of minimum weight select two trees with the largest number of vertices to combine at each stage of the algorithm. Second, among the trees of minimum weight select two trees with the smallest number of vertices at each stage.

b) Compute the average number of bits required to encode a symbol with each code and compute the variances of this number of bits for each code. Which tiebreaking procedure produced the smaller variance in the number of bits required to encode a symbol?

A full \({\bf{m - }}\)ary tree \(T\) has \(81\) leaves and height \(4\).

\({\bf{a)}}\)Give the upper and lower bounds for \({\bf{m}}\).

\({\bf{b)}}\)What is \({\bf{m}}\) if \(T\) is also balanced?

A complete \({\bf{m - }}\)ary tree is a full \({\bf{m - }}\)ary tree in which every leaf is at the same level.

Show that a cut set of a graph must have at least one edge in common with any spanning tree of this graph

construct a Huffman code for the letters of the English alphabet where the frequencies of letters in typical English text are as shown in this table.

Frequency Letter

Suppose that \({\bf{m}}\) is a positive integer with \({\bf{m}} \ge {\bf{2}}\). An m-ray Huffman code for a set of \({\bf{N}}\) symbols can be constructed analogously to the construction of a binary Huffman code. At the initial step, \(\left( {\left( {{\bf{N - 1}}} \right){\bf{ mod }}\left( {{\bf{m - 1}}} \right)} \right){\bf{ + 1}}\) trees consisting of a

single vertex with least weights is combined into a rooted tree with these vertices as leaves. At each subsequent step ,the \({\bf{m}}\) trees of least weight are combined into an m-ray tree.

Prove that Sollin’s algorithm produces a minimum spanning tree in a connected undirected weighted graph.

Devise an algorithm for constructing the spanning forest of a graph based on breadth-first searching.