Chapter 11: Trees

Devise an algorithm for constructing the spanning forest of a graph based on deleting edges that form simple circuits.

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.

40.

Suppose that G is a directed graph with no circuits. Describe how depth-first search can be used to carry out a topological sort of the vertices of G.

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 \({\bf{39--41}}\) find every vertex that is a center in the given tree.

41.

How many children does the root of the game tree for checkers have? How many grandchildren does it have?

Devise an algorithm for constructing the spanning forest of a graph based on depth-first searching.

Suppose that \({\bf{e}}\) is an edge in a weighted graph that is incident to a vertex v such that the weight of \({\bf{e}}\) does not exceed the weight of any other edge incident to v. Show that there exists a minimum spanning tree containing this edge.

Devise an algorithm for constructing the spanning forest of a graph based on breadth-first searching.

Show that a center should be chosen as the root to producea rooted tree of minimal height from an unrooted tree.

How many children does the root of the game tree for nim have and how many grandchildren does it have if the starting position is

a) piles with four and five stones, respectively.

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

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

d) piles with two, two, three, three, and five stones, respectively.