Chapter 11: Trees

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.

How many edges must be removed from a connected graph with n vertices and m edges to produce a spanning tree?

The roads represented by this graph are all unpaved. Thelengths of the roads between pairs of towns are represented by edge weights. Which roads should be pavedso that there is a path of paved roads between eachpair of towns so that a minimum road length is paved?(Note: These towns are in Nevada.

a. Define a tree.

b. Define a forest.

Show that a simple graph is a tree if and only if it contains no simple circuits and the addition of an edge connecting two nonadjacent vertices produces a new graph that has exactly one simple circuit (where circuits that contain the same edges are not considered different).

Describe the trees produced by breadth-first search anddepth-first search of the complete graph\({{\bf{K}}_{\bf{n}}}\), where n is a positive integer. Justify your answers.

Construct the binary tree with prefix codes representing these coding schemes.

a) a: 11, e:0, t: 101, s: 100

b) a: 1, e: 01, t: 001, s: 0001, n: 00001

c) a: 1010, e: 0, t: 11, s: 1011, n: 1001, i: 10001

How many leaves does a full \(3\)-ary tree with \({\bf{100}}\) vertices have?

In how many ways can the string \({\bf{\neg p}} \wedge {\bf{q}} \leftrightarrow {\bf{\neg p}} \vee {\bf{\neg q}}\) be fully parenthesized to yield an infix expression?

Suppose that the computer network connecting the cities in Figure \({\bf{1}}\) must contain a direct link between New York and Denver. What other links should be included so that there is a link between every two computer centers and the cost is minimized?