Exam Review Suggestions	
•	Define Hamiltonian circuit.
•	Find a Hamiltonian circuit for a given graph. For general graphs, there is no easy method to detect  whether the graph has one.
•	Find a minimum-cost Hamiltonian circuit using the brute force algorithm, the sorted edge algorithm, or the nearest neighbor algorithm. Which one of these would always work? Why is it not a good general method?
•	Draw a graph representation of some application; e.g. the island in the river problem 
•	Know how to use and apply the Fundamental Theorem of Counting.
•	Define a tree.
•	Know what a spanning tree is for a graph.
•	Know how to find a minimum-cost spanning tree using Kruskal’s Algorithm.  Does this produce a unique spanning tree? Does it always produce trees with the same weight?

Problems

1. Define Hamiltonian circuit.

2. a. Which (if any) of the following represent a spanning tree?

   b. Which (if any) of the following represent a Hamiltonian circuit?

         
i				    ii

iii			       	iv

3. What is the only method studied that guarantees a minimum cost Hamiltonian circuit (assuming a Hamiltonian circuit exists)? Describe it. Why isn’t it always used?

4. Given the following weighted graph:
a. Find a Hamiltonian Circuit using the sorted-edge algorithm. Indicate the order in which you selected the edges.

b. Find a Hamiltonian Circuit using the nearest-neighbor algorithm starting from A. Indicate the order in which you selected the edges.

c. Find a minimum-cost spanning tree using Kruskal’s algorithm. Indicate the order in which you selected the edges.

5. a. Use Kruskal’s algorithm to find a minimum cost spanning tree for the graph below.

b. Is your minimum cost spanning tree the only minimum cost spanning tree?  ___________ 

c. If your answer is no in part b, give another minimum cost spanning tree on the graph below.  If your answer is yes, explain why.

6. 
a. For the graph shown, use the sorted edges algorithm to find a Hamilton circuit.  

b. For the same graph (shown again for your convenience), use the nearest neighbor algorithm starting at vertex A to find a Hamilton circuit.

		Graph 6-a					      Graph 6-b

7. When going outside on a cold winter day, Jill can choose from three winter coats, five wool scarves, two pairs of boots and four hats.

a. How many outfits might her friends see her in?

b. If Jill does not wear her green scarf unless she wears the blue coat, how many outfits might her friends see her in?

8. You have 3 ties, 4 pairs of pants, and 6 shirts.

a. How many outfits can you make if any outfit must contain exactly one tie, exactly one pair of pants, and exactly one shirt? 

b. How many outfits can you make if any outfit must contain exactly one shirt, exactly one pair of pants, but may contain exactly one tie or no tie? 

9. A lottery game requires that a person select a letter followed by five digits, provided that the five digits cannot all be 0. How many different ways are there to fill out a lottery ticket?