Chapter 11: Trees

Draw the subtree of the game tree for tic-tac-toe beginning at each of these positions. Determine the value of each of these subtrees.

Let \(n\) be a power of 2. Show that \(n\) numbers can be added in \(\log n\) steps using a tree-connected network of \(n - 1\) processors.

Devise an algorithm based on breadth-first search for finding the connected components of a graph.

How many nonisomorphic caterpillars are there with six vertices?

Explain how breadth-first search and how depth-first search can be used to determine whether a graph is bipartite.

Suppose that the first four moves of a tic-tac-toe game are as shown. Does the first player (whose moves are marked by Xs) have a strategy that will always win?

The eccentricity of a vertex in an unrooted tree is the length of the longest simple path beginning at this vertex. A vertex is called a center if no vertex in the tree has smaller eccentricity than this vertex. In Exercises 39-41 find every vertex that is a center in the given tree.

a) Prove or disprove that all trees whose edges form a single path are graceful.

b) prove or disprove that all caterpillars are graceful.

The eccentricity of a vertex in an unrooted tree is the length of the longest simple path beginning at this vertex. A vertex is called a center if no vertex in the tree has smaller eccentricity than this vertex. In Exercises 39-41find every vertex that is a center in the given tree.

39.

Show that if a game of nim begins with two piles containing the same number of stones, as long as this number is at least two, then the second player wins when both players follow optimal strategies.