Chapter 11: Trees

Show that any well-formed formula in prefix notation over a set of symbols and a set of binary operators contains exactly one more symbol than the number of operators.

How many edges are there in a forest of \({\bf{t}}\) trees containing a total of \({\bf{n}}\) vertices?

Show that every finite simple graph has a spanning forest.

In Exercises 31-33 find a degree-constrained spanning tree of the given graph where each vertex has degree less than or equal to 3, or show that such a spanning tree does not exist.

Explain how a tree can be used to represent the table of contents of a book organized into chapters, where each chapter is organized into sections, and each section is organized into subsections.

How many trees are in the spanning forest of a graph?

Prove that Kruskal’s algorithm produces minimum spanning trees.

Give a definition of well-formed formulae in postfix notation over a set of symbols and a set of binary operators.

Show that Huffman codes are optimal in the sense that they represent a string of symbols using the fewest bits among all binary prefix codes.

In Exercises 31-33 find a degree-constrained spanning tree of the given graph where each vertex has degree less than or equal to 3, or show that such a spanning tree does not exist.