1. A delivery truck must deliver packages to 6 different store locations (A, B, C, D, E, and F). The trip must start and end at A.

The graph below shows the distances (in miles) between locations. We want to minimize the total distance traveled.

The cheapest-link algorithm applied to the graph yields the following solution: (PICK 1-6)

1.		A, D, F, E, C, B, A.
2.		A, C, D, B, E, F, A.
3.		A, E, F, C, B, D, A.
5.		A, B, C, D, E, F, A.
6.		None of the above

2. A mail truck must deliver packages to 5 different homes (A, B, C, D, and E). The trip must start and end at A.

The graph below shows the distances (in miles) between locations. We want to minimize the total distance traveled.

The cheapest-link algorithm applied to the graph yields the following solution:

		1. A, D, B, E, C, A.
		2. A, C, D, B, E, A.
		3. A, B, C, D, E, A.
		4. A, E, C, D, B, A.
		5. None of the above

3. The following graph

has a Hamilton path that starts at D and ends at G.

has a Hamilton path that starts at G and ends at E.

has a Hamilton path that starts at G and ends at F.

has no Hamilton path.

None of the above

4. The following graph

		has several Hamilton circuits, none of which contain the edge AB.
		has no Hamilton circuit.
		has a single Hamilton circuit (and its mirror-image circuit).
		has several Hamilton circuits, all of which contain the edge AD.
		None of the above

16 B 4 1014 2 15 D