1. Which of the statements below is false for the graph G shown?

2. The cost of the nearest-neighbor tour for the accompanying graph, starting at vertex 3, is _____________.

64

3. The cost associated with the TSP tour 0, 2, 1, 3, 0 in the accompanying graph is

4. The difference between the cost of a nearest-neighbor tour starting at D and the cost of a sorted-edges tour for the accompanying graph is ___________.

5. The tour 1, 3, 2, 4 is not a Hamiltonian circuit because

6. The cost of the nearest-neighbor tour (Hamiltonian circuit) that starts at vertex A for the accompanying graph is ________________.

7. The accompanying graph has no Hamiltonian circuit because

8. The cost of the sorted-edges tour (Hamiltonian circuit) for the accompanying graph is __________________.

9. Which of the following describes a Hamiltonian circuit for the graph below?

65

10. The cost of the nearest-neighbor traveling salesman tour that starts at D for the graph below is __________.

11. Suppose that after a hurricane, a van is dispatched to pick up five nurses at their homes and bring them to work at the local hospital. Which of these techniques is most likely to be useful in solving this problem?

12. If a graph has E edges and V vertices as well as a Hamiltonian circuit, then the number of edges in the Hamiltonian circuit is ___________.

13. The following graph has

14. The longest-circuit tour of vertices that arises by applying the nearest-neighbor algorithm starting at any of the sites 0, 1, 2, 3 in the graph below has a cost of __________.

15. When the sorted-edges method and nearest-neighbor method are applied to a complete graph on seven vertices with nonnegative weights,

16. The number of different lunches that Jules can design by selecting one of three meats, one of four salads, and one of six vegetables is exactly __________.

17. When the sorted-edges method is applied to the TSP where all the edges have distinct costs, which of the following must be true of the tour S obtained?

18. If a three-character password system must begin with a lowercase letter of the English alphabet followed by two decimal digits that cannot be repeated, the number of different possible passwords is ___________.

19. Paul has packed four ties, three shirts, and two pairs of pants for a trip. How many different outfits can he create if he never wears a tie?

20. A company is designing a logo with two identical lowercase letters with a single nonzero digit between the letters. A typical possible example would be d3d. The number of such logos is _____________.

21. An ice-cream shop offers 3 types of cones, 20 flavors, and 4 different toppings (crushed peanuts, crushed almonds, chocolate bits, or corn flakes). If a customer is allergic to nuts, how many different choices can she choose from?

22. A minimum-cost spanning tree for the weighted accompanying graph has weight _______ and ________ edges.

66

23. Assuming a graph with E edges and V vertices has a minimum-cost spanning tree T, which of the following statements must be true?

24. When arranged in increasing order, the weights of the edges in the following graph that are not part of the minimum-cost spanning tree selected when Kruskal’s algorithm is applied are _________, ________, _______.

25. The cost of the last edge that Kruskal’s algorithm selects to be part of a minimal-cost spanning tree for the weighted graph below is _________.

26. Assume that every edge of a graph G has a different cost. If Kruskal’s algorithm is used to find the minimum-cost spanning tree T for graph G, which of the following statements must be true?

27. If a graph contains a circuit, which of the following statements is true?

28. The earliest completion time (in minutes) for a job with the following order-requirement digraph is ____________.

29. Assume a job has an order-requirement digraph with five tasks whose critical path is 25 minutes in length. Based on this information, what can be said about the tasks?

30. The length of the critical path in the accompanying order-requirement digraph is ____________ minutes.