Quiz 7         MAT 118, Spring 2003

PRINT your Name: Solution

1. A trip is planned that will start in New York, and visit each of the cities Chicago, Denver, Dallas, Kansas City, Miami, and return. Use the greedy algorithm to plan such a trip in an attempt to minimize the distance travelled. (That is, use the greedy algorithm to find a short Hamiltonian circuit on the graph.)

Solution: The solution is shown on the graph above.

Using the greedy algorithm, we first mark the shortest path. This is the one between Chicago and Kansas City, of length 400. Then we continue marking the next shortest paths, as long as they don't either make a circuit before we've visited all the vertices, or make a 3-way intersection (chicken-foot). So, we next mark the path of length 450 (Kansas City-Dallas). The next shortest edge (600) cannot be used, so we then mark the Chicago-New York edge (700) and Dallas-Denver (780). Again, we can't use the edge of length 800, nor of 1010. We use the New York-Miami edge (length 1050), and finally, we must use the Miami-Denver edge, no matter what its length.

2. Use Prim's (nearest neighbor) algorithm to find a minimal spanning tree for the graph below.

Solution: The solution is shown on the graph above.

Recall that the minimal spanning tree is a tree connecting all the vertices, such that the sum of the weights of the edges is as small as possible. For Prim's algorithm, we begin by picking any vertex, and mark the edge of least weight connected to it. We start with the vertex in the upper right corner of the graph, and mark the edge of weight 1. Then, for Prim's algorithm, we ``grow our tree'' by marking the edge of least weight that is connected to edges already marked, provided it does not make a circuit. So, our graph grows as follows: First, we mark the edge of length 2, and then the edge of length 3. Next, we take the edge of lenth 2, and have so far joined the four vertices on the right side of the graph. We don't use the edge of length 5, since it would make a circuit.

Now we are forced to use the edge of length 8, since it is the only usable edge which meets the graph we have so far. Now we take the vertical edge of length 3, and the horizontal edge of length 5. Then we have the edge of length 2 available to us, so we use it, and the diagonal edge of length 1, as well. Using the remaining edge of length 4 and the horizontal one of length 3 finishes the tree for us; we have now joined all the vertices, and we are done.

Scott Sutherland 2003-04-05