Chapter 11: Trees

Show that an \({{\bf{S}}_{\bf{k}}}\)-tree has \({{\bf{2}}^{\bf{k}}}\) vertices and a unique vertex at level k. This vertex at level k is called the handle.

Suppose \({\bf{1000}}\) people enter a chess tournament. Use a rooted tree model of the tournament to determine how many games must be played to determine a champion, if a player is eliminated after one loss and games are played until only one entrant has not lost. (Assume there are no ties.)

Describe the trees produced by breadth-first search anddepth-first search of the complete bipartite graph \({{\bf{K}}_{{\bf{m,n}}}}\), starting at a vertex of degree m, where m and n are positive integers. Justify your answers.

what are the codes for a, e, i, k, o, p, and u if the coding scheme is represented by this tree?

In how many ways can the string \({\bf{A}} \cap {\bf{B - A}} \cap {\bf{B - A}}\) be fully parenthesized to yield an infix expression?

Find a spanning tree with minimal total weight containing the edges \(\left\{ {{\bf{e, i}}} \right\}\) and \(\left\{ {{\bf{g, k}}} \right\}\) in the weighted graph in Figure \(3\).

Suppose that T is an \({{\bf{S}}_{\bf{k}}}\)-tree with handle v. Show that T can be obtained from disjoint trees\({{\bf{T}}_{\bf{0}}}{\bf{,}}{{\bf{T}}_{\bf{1}}}{\bf{,}}...{\bf{,}}{{\bf{T}}_{{\bf{k - 1}}}}\) with roots\({{\bf{r}}_{\bf{0}}}{\bf{,}}{{\bf{r}}_{\bf{1}}}{\bf{,}}...{\bf{,}}{{\bf{r}}_{{\bf{k - 1}}}}\), respectively, where v is not in any of these trees, where \({{\bf{T}}_{\bf{i}}}\)is an \({{\bf{S}}_{\bf{i}}}\)-tree for \({\bf{i = 0,1,}}...{\bf{,k - }}1\), by connecting v to \({{\bf{r}}_{\bf{0}}}\) and \({{\bf{r}}_{\bf{i}}}\) to \({{\bf{r}}_{{\bf{i + 1}}}}\) for \({\bf{i = 0,1,}}...{\bf{,k - 2}}\).

Given the coding scheme a: 001, b: 0001, e: 1, r: 0000,s: 0100, t: 011, x: 01010, find the word represented by,

a) 01110100011.

b) 0001110000.

c) 0100101010.

d) 01100101010.

Describe an algorithm for finding a spanning tree with minimal weight containing a specified set of edges in a connected weighted undirected simple graph.

Draw the ordered rooted tree corresponding to each of these arithmetic expressions written in prefix notation. Then write each expression using infix notation.

1. \({\bf{ + }} * {\bf{ + - 53214}}\)
2. \( \uparrow {\bf{ + }}23{\bf{ - }}51\)
3. \( * {\bf{/93 + }} * {\bf{24 - 76}}\)