Chapter 11: Trees

Show that the vertex of the largest degree in \({{\bf{B}}_{\bf{k}}}\) is the root.Show that the vertex of the largest degree in \({{\bf{B}}_{\bf{k}}}\) is the root.

Describe the trees produced by breadth-first search anddepth-first search of the wheel graph\({{\bf{W}}_{\bf{n}}}\), starting at the vertex of degree n, where n is an integer with n ≥ 3. (See Example 7 of Section 10.2.) Justify your answers.

a. Represent \(\left( {{\bf{A}} \cap {\bf{B}}} \right){\bf{ - }}\left( {{\bf{A}} \cup \left( {{\bf{B - A}}} \right)} \right)\) using an ordered rooted tree.Write this expression in

b. prefix notation.

c. postfix notation.

d. infix notation.

How many edges does a full binary tree with \({\bf{1000}}\) internal vertices have?

Show that there is a unique minimum spanning tree in a connected weighted graph if the weights of the edges are all different.

Which of these codes are prefix codes?

a) a: 11, e: 00, t: 10, s: 01

b) a: 0, e: 1, t: 01, s: 001

c) a: 101, e: 11, t: 001, s: 011, n: 010

d) a: 010, e: 11, t: 011, s: 1011, n: 1001, i: 10101

a. Describe Kruskal's algorithm and Prim's algorithm for finding minimum spanning trees.

b. Illustrate how Kruskal's algorithm and Prim's algorithm are used to find a minimum spanning tree, using a weighted graph with at least eight vertices and \(15\) edges.

Draw an\({{\bf{S}}_{\bf{k}}}\)-tree for \({\bf{k = 0,1,2,3,4}}\).

Which of these graphs are trees?

(a)

(b)

(c)

(d)

(e)

(f)

Build a binary search tree for the word’s banana, peach, apple, pear, coconut, mango, and papaya using alphabetical order.