Chapter 11: Trees

What does each of these represent in an organizational tree?

\(\left( {\bf{a}} \right)\)the parent of a vertex

\(\left( {\bf{b}} \right)\)a child of a vertex

\(\left( {\bf{c}} \right)\)a sibling of a vertex

\(\left( {\bf{d}} \right)\)the ancestors of a vertex

\(\left( {\bf{e}} \right)\)the descendants of a vertex

\(\left( {\bf{f}} \right)\)the level of a vertex

\(\left( {\bf{g}} \right)\)the height of the tree

Show that a degree-constrained spanning tree of a simple graph in which each vertex has degree not exceeding 2 consists of a single Hamilton path in the graph.

Suppose that we vary the payoff to the winning player in the game of nim so that the payoff is n dollars when n is the number of legal moves made before a terminal position is reached. Find the payoff to the first player if the initial position consists of

a) two piles with one and three stones, respectively.

b) two piles with two and four stones, respectively.

c) three piles with one, two, and three stones, respectively.

Explain how to use breadth-first search to find the length of a shortest path between two vertices in an undirected graph.

Answer the same questions as those given in Exercise \(34\) for a rooted tree representing a computer file system.

Prove that the reverse-delete algorithm always producesa minimum spanning tree when given as input a weightedgraph with distinct edge weights. (Hint: Use Exercise \(33\).)

A tree with n vertices is called graceful if its vertices can be labelled with the integers 1, 2,…, n such that the absolute values of the difference of the labels of adjacent vertices are all different. Show that these trees are graceful.

Suppose that in a variation of the game of nim we allow a player to either remove one or more stones from a pile or merge the stones from two piles into one pile as long as at least one stone remains. Draw the game tree for this variation of nim if the starting position consists of three piles containing two, two, and one stone, respectively. Find the values of each vertex in the game tree and determine the winner if both players follow an optimal strategy.

Devise an algorithm based on breadth-first search that determines whether a graph has a simple circuit, and if so, finds one.

Which of the graphs in Exercise 35 are caterpillars?