Chapter 11: Trees

Three couples arrive at the bank of a river. Each of the wives is jealous and does not trust her husband when he is with one of the other wives (and perhaps with other people), but not with her. How can six people cross to the other side of the river using a boat that can hold no more than two people so that no husband is alone with a woman other than his wife? Use a graph theory model.

Draw the game tree for the game of tic-tac-toe for the levels corresponding to the first two moves. Assign the value of the evaluation function mentioned in the text that assigns to a position the number of files containing no Os minus the number of files containing no Xs as the value of each vertex at this level and compute the value of the tree for vertices as if the evaluation function gave the correct values for these vertices.

Show that a tree has either one center or two centers that are adjacent.

Let G be a connected graph. Show that if T is a spanning tree of G constructed using depth-first search, then an edge of G not in T must be a back edge, that is, it must connect a vertex to one of its ancestors or one of its descendants in T.

Show that if no two edges in a weighted graph have the same weight, then the edge with least weight incident to a vertex v is included in every minimum spanning tree.

Show that every tree can be colored using two colors. The rooted Fibonacci trees \({\bf{Tn}}\) are defined recursively in the following way. \({\bf{T1}}\)and\({\bf{T}}2\) are both the rooted tree consisting of a single vertex, and for \({\bf{n = 3, 4,}}...{\bf{,}}\) the rooted tree \({\bf{Tn}}\) is constructed from a root with \({\bf{Tn - }}1\) as its left subtree and \({\bf{Tn - 2}}\) as its right subtree.

Use pseudocode to describe an algorithm for determining the value of a game tree when both players follow a min-max strategy.

When must an edge of a connected simple graph be in every spanning tree for this graph?

Find a minimum spanning tree of each of these graphs where the degree of each vertex in the spanning tree does not exceed 2.

Draw the first seven rooted Fibonacci trees.