Chapter 11: Trees

Can there be two different simple paths between the vertices of a tree?

How many nonisomorphic rooted trees are there with six vertices?

Show that a full \({\bf{m - }}\)ary balanced tree of height \(h\) has more than \({{\bf{m}}^{{\bf{h - 1}}}}\) leaves.

Show that when given as input an undirected graph with \(n\) vertices, no more than \(\left\lfloor {\frac{n}{{{2^k}}}} \right\rfloor \) trees remain after the first step of Sollin's algorithm has been carried out and the second step of the algorithm has been carried out \({\bf{k - 1}}\) times.

A spanning forest of a graph Gis a forest that contains every vertex of G such that two vertices are in the same tree of the forest when there is a path in Gbetween these two vertices.

Consider the three symbols \({\bf{A, B, and C}}\) with frequencies \({\bf{A:0}}{\bf{.80, B:0}}{\bf{.19, C:0}}{\bf{.01}}\).

a) Construct a Huffman code for these three symbols.

b) Form a new set of nine symbols by grouping together blocks of two symbols, \({\bf{AA, AB, AC, BA, BB, BC, CA, CB, and CC}}\). Construct a Huffman code for these nine symbols, assuming that the occurrences of symbols in the original text are independent.

c) Compare the average number of bits required to encode text using the Huffman code for the three symbols in part (a) and the Huffman code for the nine blocks of two symbols constructed in part (b). Which is more efficient?

Which of these are well-formed formulae over the symbols \(\left\{ {{\bf{x,y,z}}} \right\}\) and the set of binary operators \(\left\{ {{\bf{ \ast , + ,}} \circ } \right\}\)?

1. \({\bf{ \ast + + xyx}}\)
2. \( \circ {\bf{xy \ast xz}}\)
3. \({\bf{ \ast }} \circ {\bf{xz \ast \ast xy}}\)
4. \({\bf{ \ast + }} \circ {\bf{xx}} \circ {\bf{xxx}}\)

Show that if every circuit not passing through any vertex other than its initial vertex more than once in a connected graph contains an odd number of edges, then this graph must be a cactus.

Show that Sollin’s algorithm requires at most \({\bf{logn}}\) iterations to produce a minimum spanning tree from a connected undirected weighted graph with \({\bf{n}}\) vertices.

Given\({\bf{n + 1}}\) symbols \({{\bf{x}}_{\bf{1}}}{\bf{,}}\,{{\bf{x}}_{\bf{2}}}{\bf{,}}\,...\,{\bf{,}}{{\bf{x}}_{{\bf{n,}}\,}}{{\bf{x}}_{{\bf{n + 1}}}}\) appearing\({\bf{1,}}\,{{\bf{f}}_{\bf{1}}}{\bf{,}}\,{{\bf{f}}_{\bf{2}}}{\bf{,}}\,...\,{\bf{,}}{{\bf{f}}_{\bf{n}}}\) times in a symbol string, respectively, where \({{\bf{f}}_{\bf{j}}}\) is the\({{\bf{j}}^{{\bf{th}}}}\) Fibonacci number, what is the maximum number of bits used to encode a symbol when all possible tie-breaking selections are considered at each stage of the Huffman coding algorithm?