1.	Construct a complete graph on 4 vertices.	

2.	Construct a complete graph whose vertices represent the six largest islands of Hawaii: Kauai, Oahu, Molokai, Lanai, Maui, and Hawaii.	

3.	Construct an example of a spanning tree on the graph given below.

4.	Construct an example of a graph with no Hamiltonian circuit.	

5.	Construct a digraph for the following tasks necessary when building a house: get a building permit, install wiring, pour foundation, build walls, build doghouse, pass final inspection.	

6.	Identify six tasks necessary when building a sandwich, and construct a digraph for these tasks.	

7.	Identify six tasks necessary when preparing for a picnic, and construct a digraph for these tasks.	

8.	Use the brute force algorithm to solve the traveling salesman problem for the graph of the four cities shown below.

9.	Use the brute force algorithm to solve the traveling salesman problem for the graph of the four cities shown below.

10.	Use the brute force algorithm to solve the traveling salesman problem for the graph of the four cities shown below.

11.	You own a chain of 12 apartment complexes (including your residence) and you want to plan a trip to visit each of your  properties. If it takes 1/2 minute to compute the total length of a tour, how long will it take to apply the brute force algorithm to find the optimal tour? 	

12.	You own a chain of 10 one-day photo development kiosks and a lab where the photos are developed. Each morning and evening a delivery truck leaves the lab, visits each kiosk and returns to the lab. If it takes 1/3 minute to compute the total length of a tour, how long will it take to apply the brute force algorithm to find the optimal tour for the delivery truck? 	

13.	You want to create a mileage grid showing the distance between every pair of the 50 U.S. state capitals. How many numbers will you have to compute? 	

14.	You want to create a mileage grid showing the distance between every pair of the 10 Canadian provincial and territorial capitals. How many numbers will you have to compute? 	

15.	The local cafe offers three different entrees, 10 different vegetables, and four different salads. A "blue plate special" includes an entree, a vegetable, and a salad. How many different ways can a special be constructed? 	

16.	A nearby ice cream shop offers 31 different flavors and three different types of cones. How many different single scoop cones can be ordered? 	

17.	In some states, license plates use a mixture of letters and numerals. How many possible plates could be constructed using three letters followed by three numerals? 	

18.	In some states, license plates use a mixture of letters and numerals. How many possible plates could be constructed using two letters followed by four numerals? 	

19.	What is an advantage of a heuristic algorithm? 	

20.	What is a disadvantage of a heuristic algorithm? 	

21.	What is critical about the critical path of an order-requirement digraph? 	

22.	Can a graph have an Euler circuit, but not a Hamiltonian circuit? Explain your answer.	

23.	Can a graph have a Hamiltonian circuit, but not an Euler circuit? Explain your answer.	

24.	Will the nearest-neighbor algorithm ever use the most expensive edge of a graph? 	

25.	The route of a neighborhood garbage truck generally follows an Euler circuit. Under what circumstances should it instead follow a Hamiltonian circuit? 	

26.	The route of a delivery truck generally follows a Hamiltonian circuit. Under what circumstances should it instead follow an Euler circuit? 	

27.	In the graph below, add wiggly edges to indicate a Hamiltonian circuit.

28.	In the graph below, add wiggly edges to indicate a Hamiltonian circuit.

29.	Construct an example of a connected graph that does not have a Hamiltonian circuit.	

30.	Construct an example of a connected graph that has a Hamiltonian circuit but does not have an Euler circuit.	

31.	A connected graph H has a spanning tree with 50 edges. How many vertices does the spanning tree have? How many vertices does H have? What can one say about the number of edges H has? 	

Answer Key

1.	
	
2.	
	
3.	
	
4.	
	
5.	
	
6.	
	
7.	
	
8.	Route ABCDA and ACBDA have cost 155.  Route ABDCA has (minimum) cost 120.	
9.	Route PQRSP and PQSRP have (minimum) cost 1200.  Route PRQSP has cost 1400.	
10.	Only one route, with cost 594.	
11.	(11!/2)(1/2) = 9979200 minutes, approximately 19 years.	
12.	(9!/2)(1/3) = 60480 minutes, or 42 days.	
13.	(50)(49)/2 = 1225	
14.	(10)(9)/2 = 45	
15.	120	
16.	93	
17.	263 · 103 = 17,576,000	
18.	264 · 102 = 6,760,000	
19.	Fast.	
20.	Not always optimal.	
21.	It requires the critical or essential amount of time required to complete the project.	
22.	
	
23.	
	
24.	Yes.	
25.	If it only picks up at central locations.	
26.	If it delivers to every house.	
27.	(bold lines should be squiggly)
	
28.	(bold lines should be squiggly)
	
29.	Answers will vary. One solution is:
	
30.	Answers will vary. One solution is:
	
31.	The spanning tree has 51 vertices. H also has 51 vertices. H must have at least 50 edges.