1. Find a weighted graph for which the weight of a minimum weight spanning tree is not equal to the weight of any minimum distance tree for that graph.

2. A dog, a goat and a bag of tin cans are on the Amherst side of the Connecticut river. A mathematician with a small boat is supposed to bring all of them over to the Smith College picnic. Unfortunately she can only bring one of these items over at a time. The dog and the goat can not be left alone on the shore (without the mathematician) nor can the goat and the tin cans be left alone. Find a scheme to get everything across the river (do not use the bridge!)(Use a search tree.)

3. Suppose we are given three pitchers of sizes 10 cups, 7 cups and 4 cups. Initially the 10 cup pitcher is full and the other two empty. We are allowed to pour water from one pitcher to another providing that each time we pour, either the receiving pitcher gets full or the pouring pitcher gets emptied. Is there a way to get exactly 2 cups in either the 7-cup or 4-cup pitcher? If so, what is the quickest way to do it? (Use a search tree.)

4. A city is planning on building a new fire station. They would like to locate it in a place where it is closest to the most things. In other words, so that the shortest paths from the fire station to other locations in the city are relatively small. Formally, the eccentricity of a vertex, x is the length of the longest path originating at x. Equivalently, it is the maximum value of d(x,v) taken over all vertices v. A vertex is a center of the graph if its eccentricity is smallest.

(i) Find the eccentricity of each vertex in both trees of figure 10.6. Find the center of each tree as well.

(ii) Show by example that a graph can have more than one vertex in the center.

(iii) Describe an algorithm based on BFS that give the eccentricity of every vertex in the graph.

Remember to do the problems from the text: 8.# 2,3,4,7 and 11.# 9.