2.1 Hamiltonian Circuits

1. For the accompanying graphs (a) through (c), write down a Hamiltonian circuit starting at X₂.

67

2. Construct a grid graph with m rows (m at least 3) and n columns (see Figure 2.2b for a 4-by-4 grid graph) that

3. For the accompanying graphs (a) through (c), write down, if possible, a Hamiltonian circuit starting at X₃.

4.

5. For the accompanying graphs (a) through (c), write a Hamiltonian circuit starting at X₃.

68

6. Refer to the accompanying graph.

7. If the edge X₂X₃ is erased from each of the graphs in Exercise 5, does the resulting graph still have a Hamiltonian circuit?

8.

9.

10.

11. Suppose two Hamiltonian circuits are considered different if the collections of edges that they use are different. How many other Hamiltonian circuits can you find in the graph in Figure 2.1 that are different from the two discussed?

12.

13.

69

14. Explain why the graph below has no Hamiltonian circuit.

15. Use the graph shown in Exercise 14 to help you construct a connected graph for which every vertex has valence 3 and that does not have a Hamiltonian circuit.

16. Explain why the tour CFECBADBC is not a Hamiltonian circuit for the accompanying graph. Does this graph have a Hamiltonian circuit?

17. Do the following graphs have Hamiltonian circuits? If not, can you demonstrate why not?

18. If an edge from X₂ to X₅ is added to each graph in Exercise 17, do the new graphs that result have a Hamiltonian circuit?

19. For each of the accompanying graphs, determine whether there is a Hamiltonian circuit.

20.

Can you think of a real-world situation in which finding a Hamiltonian circuit in an grid graph would represent a solution to the problem? If an grid graph has no Hamiltonian circuit, can you find a tour that repeats a minimum number of vertices and starts and ends at the same vertex?

70

21. A Hamiltonian path in a graph is a tour of the vertices of the graph that visits each vertex once and only once and starts and ends at different vertices.

22. Using the terminology of Exercise 21, draw a graph that has

23. To practice your understanding of the concepts of Euler circuits and Hamiltonian circuits, determine for the accompanying graphs (a) through (d) whether there is an Euler circuit and/or a Hamiltonian circuit. If so, write it down.

24.

25. If an edge is added from the vertex with subscript 3 to the vertex with subscript 6 in each graph in Exercise 23, which of the resulting graphs will have Hamiltonian circuits and which will have Euler circuits?

26. Find a family of graphs, none of which has a Hamiltonian circuit but for which adding a single edge to the first graph in the family creates a Hamiltonian circuit, adding two edges to the second graph in the family creates a Hamiltonian circuit, and so forth.

27. A Hamiltonian path in a graph is a tour of the vertices that visits each vertex once and only once and that starts and ends at different vertices.

71

28.

29. The notes C, D, E, F, G, A, and B are to be used to form an ordered five-note musical logo. In how many ways can this be done under the following circumstances?

30. A lottery game requires a person to select an uppercase or lowercase letter followed by two different odd digits. How many choices can a customer make?

31.

32. To encourage her son to try new things, a mother offers to take him for a dish of ice cream with a topping once a week, for as many weeks as he does not get the same choice as on a previous occasion. If the store offers 12 flavors and 6 toppings, for how many weeks will she have to do this if her son never picks either of the two types of chocolate ice cream or the three types of nut topping that the store carries?

33. A large corporation has found that it has “outgrown” its current code system for routing interoffice mail. The current system places a code of three ordered, distinct nonzero digits on the mail. The new proposal calls for the use of two ordered capital letters. Does the new system have more code numbers than the old system? If so, how many more locations will the new system enable the company to encode over the current system?

34. Repeat Exercise 29a, except that exactly one of the notes in the musical logo must be a sharp and the note chosen to be sharped cannot appear elsewhere (e.g., BCD#AG, where D# denotes D sharp).

35.

36. A restaurant offers 6 soups, 10 entrees, and 8 desserts. How many different choices for a meal can a customer make if one selection is made from each category? If 3 of the desserts are pies and the customer will never order pie, how many meals can the customer choose?

37. In the last several years, heavily populated regions that previously had only one area code have been divided into service areas with more than one area code. What is the largest number of different phone numbers that can be served using one area code? If an area code cannot begin with a zero, how many different area codes are possible?

38.

2.2 Traveling Salesman Problem

2.3 Helping Traveling Salesmen

39. Draw complete graphs with four, five, and six vertices. How many edges do these graphs have? Can you generalize to n vertices? How many TSP tours would these graphs have? (Tours yielding the same Hamiltonian circuit are considered the same.)

40. Calculate the values of , , , , , and . Then find the number of TSP tours in the complete graph with eight vertices.

41. The following table shows the mileage between four cities: Springfield, Ill. (); Urbana, Ill. (); Effingham, Ill. (); and Indianapolis, Ind. ().

72

42. After a party at her house, Francine () has agreed to drive Mary (M), Rachel (), and Constance () home. If the times (in minutes) to drive between her friends’ homes are shown below, what route gets Francine back home the quickest?

43. In Exercise 42, what route would Francine have to follow to get home as quickly as possible, assuming she promised to drive Constance home first?

44. In Exercise 42, Francine is planning to deliver her friends home and then spend the night at Rachel's house. What would her fastest route be?

45. A religious charity arranges free pickups for donated goods to encourage such donations but would like to keep its pickup costs low. The accompanying diagram shows the estimated amounts of time to get between the charity () and the locations of the three pickups scheduled for Wednesday.

46. An organization that delivers meals to the needy elderly must deliver food to three clients and wants to keep down its costs. Typical times to get between its home site H and the clients are given in the accompanying graph.

73

47. Starting from the location where she moors her boat (), a fisherwoman wishes to visit three areas—, , and —where she has set fishing nets. If the times (in minutes) between the locales are given in the accompanying figure, what route to visit the three sites and return to the mooring place would be optimal?

48.

49. An airport limo must take its five passengers from the airport to different downtown hotels. Is this a traveling salesman problem, a Chinese postman problem, or an Euler circuit problem?

50. For each of the accompanying graphs with weights, apply the nearest-neighbor method (starting at vertex A) and the sorted-edges method to find (it is hoped) a cheap tour.

74

51. The accompanying figure represents a town where there is a sewer located at each corner (where two or more streets meet). After every thunderstorm, the department of public works wishes to have a truck start at its headquarters (at vertex H) and make an inspection of sewer drains to be sure that leaves are not clogging them. Can a route start and end at H that visits each corner exactly once? (Assume that all the streets are two-way streets.) Does this problem involve finding an Euler circuit or a Hamiltonian circuit?

Assume that at equally spaced intervals along the blocks in this graph, there are storm sewers that must be inspected after each thunderstorm to see if they are clogged. Is this a Hamiltonian circuit problem, an Euler circuit problem, or a Chinese postman problem? Find an optimal tour to do this inspection.

52.

53. Construct an example of a complete graph of five vertices, with distinct weights on the edges for which the nearest-neighbor algorithm starting at a particular vertex and the sorted-edges algorithm yield different solutions for the traveling salesman problem. Can you find a five-vertex complete graph with weights on the edges in which the optimal solution, the nearest- neighbor solution, and the sorted-edges algorithm solution are all different?

54. If the brute force method of solving a 20-city TSP is employed, use a calculator to determine how many Hamiltonian circuits must be examined. How long would it take to determine the minimum- cost tour if the cost of tours could be computed at the rate of 1 billion per second? (Convert your answer to years by seeing how many years are equivalent to a billion seconds!)

55. Suppose one has found an optimal tour for a given 10-city TSP to have weight 4200. Now suppose the weights on the edges of the complete graph are increased by 50. What can you say about the optimal tour and its weight?

2.4 Minimum-Cost Spanning Trees

56. For each graph below, explain why it is or is not a tree.

57. For each of the accompanying diagrams, explain why the wiggly edges are not

75

58. Find all the spanning trees in the accompanying graphs.

59. Use Kruskal's algorithm to find a minimum-cost spanning tree for the following graphs (a), (b), (c), and (d). In each case, what is the cost associated with the tree?

60. A connected graph G has 14 vertices. How many edges does a spanning tree of G have? How many vertices does a spanning tree of G have? What can one say about the number of edges G has?

61. A connected graph H has a spanning tree with 26 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?

62. A large company wishes to install a pneumatic tube system that would enable small items to be sent between any of 10 locales, possibly by using relay. If the nonprohibitive costs (in $100) are shown in the accompanying graph model, between which sites should the tube be installed to minimize the total cost?

63. If the weight of each edge in Exercise 60 is increased by 3, will the tree that achieves minimum cost for the new collection of weights be the same as the one that achieves minimum cost for the original set of weights?

64. Give examples of real-world situations that can be modeled using a weighted graph and for which finding a minimum-cost spanning tree for the graph would be of interest.

65. Can Kruskal’s algorithm be modified to find a maximum-weight spanning tree? Can you think of an application for finding a maximum-weight spanning tree?

76

66. Find the cost of providing a relay network between the six cities with the largest populations in your home state, using the road distances between the cities as costs. Does it follow that the same solution would be obtained if air distances were used instead?

67. Would there ever be a reason to find a minimum-cost spanning tree for a weighted graph in which the weights on some of the edges were negative? Would Kruskal’s algorithm still apply?

68. Suppose G is a graph such that all the weights on its edges are different numbers. Show that there is a unique minimum-cost spanning tree.

69. Two spanning trees of a (weighted) graph are considered different if they use different edges. Show that the following graph has different minimum-cost spanning trees, though all these different trees have the same cost.

70. Let G be a graph with weights assigned to each edge. Consider the following algorithm:

If in the new graph two or more edges join a pair of vertices, delete all but the cheapest. Continue to call the new vertex V.

(d) Repeat steps (b) and (c) until a single point is obtained. The edges selected in the course of this algorithm (called Prim’s algorithm) form a minimum-cost spanning tree. Apply this algorithm to the accompanying graphs.

71. Determine whether each of the following statement: is true or false for a minimum-cost spanning tree T for a weighted connected graph G:

72. In the accompanying graphs, the number in the circle for each vertex is the cost of installing equipment at the vertex if relaying must be done at the vertex, while the number on an edge indicates the cost of providing service between the endpoints of the edge.

In each case, find the minimum cost (allowing relays) for sending messages between any pair of vertices, taking vertex relay costs into account.

77

Would your answer be different if vertex relay costs were neglected? (Warning: Kruskal’s algorithm cannot be used to answer the first question. This problem illustrates the value of having an algorithm over relying on “brute force.”)

73.

74.

75. The accompanying figure represents four objects using a tree with weights on the edges. Construct a table with four rows and four columns recording how “close” pairs of vertices in the tree are to each other. To find how close a pair of objects is, add together the weights along the path that joins these two objects.

2.5 Critical-Path Analysis

76. Find the earliest completion time and critical paths for the accompanying order-requirement digraphs.

77. Find the earliest completion time and critical paths for the following order-requirement digraphs.

78

78. Construct an example of an order-requirement digraph with exactly three different critical paths.

79. In the accompanying order-requirement digraph, determine which tasks, if shortened, would reduce the earliest completion time and which would not. Then find the earliest completion time if task T₅ is reduced to time length 7. What is the new critical path?

80. For the order-requirement digraph in Exercise 79, find the critical path and the task(s) in the critical path whose time, when reduced the least, creates a new critical path.

81. To build a new addition on a house, the following tasks must be completed:

Construct reasonable time estimates for these tasks and a reasonable order-requirement digraph. What is the fastest time in which these tasks can be completed?

82. At a large toy store, scooters arrive unassembled in boxes. To assemble a scooter, the following tasks must be performed:

Give reasonable time estimates for these tasks and construct a reasonable order-requirement digraph. What is the earliest time by which these tasks can be completed?

83. Construct an order-requirement digraph with six tasks that has three critical paths of length 26.

Chapter Review

84. Use the nearest-neighbor method starting at D and the sorted-edges method to find a hopefully short way to deliver packages from the depot at D to the other four sites in the accompanying complete graph.

85. Mary must choose a new password where the first and last choices are possibly repeated lowercase letters; the second and third positions must be distinct capital letters; the fourth position must be a #, $, or & symbol; and the next three positions are distinct nonzero digits. In how many ways can she choose a password?

86. Does the graph G in Chapter 1, Exercise 71 (page 36), have a Hamiltonian circuit? If so, write one down that starts at H.

87. Use Kruskal’s algorithm to make cable television available for the sites in the accompanying graph, assuming that video can be relayed. The costs of putting in connections are shown.