Chapter 2 Exercises
2.1 Hamiltonian Circuits
1. For the accompanying graphs (a) through (c), write down a Hamiltonian circuit starting at X2.
1.
(a) X2X6X7X3X4X8X12X11X10X9X5X1X2
(b) X2X5X8X3X4X7X6X1X2 is one possibility, as is X2X1X4X3X8X5X6X7X2.
(c)X2X8X1X10X7X6X9X5X4X3X2 is one possibility, as is X2X1X8X9X10X7X6X5X4X3X2.
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 X3.
3.
(a) Not possible
(b) A possible answer is X3X2X11X12X6X13X20X16X17X14X10X1X4X9X15X18X19X8X7X5X3
(c) X3X4X2X5X6X1X3
4.
5. For the accompanying graphs (a) through (c), write a Hamiltonian circuit starting at X3.
5.
Possible answers include:
(a) Answers will vary. One Hamiltonian circuit is X3X1X2X4X5X6X3.
(b) X3X2X1X6X7X8X9X10X11X12X5X4X3
(c) X3X1X2X7X6X9X8X5X4X3
6. Refer to the accompanying graph.
7. If the edge X2X3 is erased from each of the graphs in Exercise 5, does the resulting graph still have a Hamiltonian circuit?
7.
(a) Yes
(b) Yes
(c) Yes
8.
9.
9.
(a) No for (a); yes for (b); no for (c)
(b) No longer possible to send messages between these two sites
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?
11.
Answers will vary.
12.
13.
13.
(a) Yes for both.
(b) Answers will vary.
(c) Add edges X2X8,X8X6,X6X4, and X4X2.
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.
15.
Drawings can vary. Possible renderings include the following:
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?
17.
(a) No
(b) No
18. If an edge from X2 to X5 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.
19.
(a) Yes
(b) No
(c) No
20.
Can you think of a real-world situation in which finding a Hamiltonian circuit in an m×n grid graph would represent a solution to the problem? If an m×n 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?
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.
21.
(a) Yes
(b) No
(c) Answers will vary.
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.
23.
(a) Hamiltonian circuit: yes; Euler circuit: yes; additional answers will vary.
(b) Hamiltonian circuit: yes; Euler circuit: yes
(c) Hamiltonian circuit: yes; Euler circuit: no
(d) Hamiltonian circuit: no; Euler circuit: yes; additional answers will vary.
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?
25.
(a) Hamiltonian circuit: yes; Euler circuit: no
(b) Hamiltonian circuit: yes; Euler circuit: no
(c) Hamiltonian circuit: yes; Euler circuit: no
(d) Hamiltonian circuit: no; Euler circuit: no
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.
27.
(a) Drawings will vary.
(b) Drawings will vary.
(c) Answers will vary.
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?
29.
(a) 2520
(b) 16,807
(c) 16,800
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.
31.
(a) 15,120
(b) 17,576
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?
33.
Yes; 172
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.
35.
(a) 17,558,424
(b) Answers will vary.
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?
37.
10,000,000; 900
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.)
39.
Drawings will vary.; 6, 10, and 15 edges, respectively; n(n−1)2 edges; 3, 12, and 60, respectively
40. Calculate the values of 5!, 6!, 7!, 8!, 9!, and 10!. 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. (S); Urbana, Ill. (U); Effingham, Ill. (E); and Indianapolis, Ind. (I).
E | I | S | U | |
E | — | 147 | 92 | 79 |
I | 147 | — | 190 | 119 |
S | 92 | 190 | — | 88 |
U | 79 | 119 | 88 | — |
41.
(a) Possible drawings include the following:
(b) Tour 1: UISEU: 480
Tour 2: USIEU: 504
Tour 3: UIESU: 446
(c) Tour 3
(d) No
(e) Tour 1; yes; yes; no
(f) Tour 2; no
42. After a party at her house, Francine (F) has agreed to drive Mary (M), Rachel (R), and Constance (C) 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?
43.
FCMRF
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 (H) and the locations of the three pickups scheduled for Wednesday.
45.
(a) HBCAH
(b) HBCAH
(c) The cheapest route costs 132 and coincides with the nearest-neighbor solution from H and the sorted-edges solution.
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.
47. Starting from the location where she moors her boat (M), a fisherwoman wishes to visit three areas—A, B, and C—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?
47.
MACBM
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?
49.
A traveling salesman 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.
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.
51.
Yes; Hamiltonian circuit; Chinese postman problem; answers will vary and require at least 9 reuses of edges.
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?
53.
Answers will vary.
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?
55.
The optimal tour is the same but its cost is now 4700.
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
57.
Diagram (a): (a) There is a circuit and wiggled edges do not include all vertices. (b) The circuit does not include all the vertices of the graph.
Diagram (b): (a) The tree does not include all vertices of the graph. (b) Not a circuit
Diagram (c): (a) Not a tree (b) Not a circuit
Diagram (d): (a) Not a tree (b) Not a circuit
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?
59.
(a) 1, 2, 3, 4, 5, 8; cost is 23.
(b) 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 6; cost is 34.
(c) 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7; cost is 60.
(d) 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6; cost is 45.
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?
61.
H’s spanning tree has 24 vertices; H has 24 vertices. H has at least 23 edges and, if there are no multiple edges, at most (24)(23)/2 edges.
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?
63.
Yes
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?
65.
Yes; additional answers will vary.
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?
67.
Yes; yes
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.
69.
There are three different trees with 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:
71.
(a) True
(b) False (unless all the edges of the graph have the same weight)
(c) True
(d) False
(e) False
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.
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.
73.
(a) Answers will vary for each edge.
(b) 5; one less than the number of vertices in the graph
(c) No (CD and AG must be included in any spanning tree.)
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.
75.
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.
77.
(a) 22; T3T2T5
(b) 30; T3T5T7
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 T5 is reduced to time length 7. What is the new critical path?
79.
T1, T5, and T7 if shortened would reduce the earliest completion time, while shortening the other tasks will not; 29; T1T4T7.
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?
81.
Answers will vary.
82. At a large toy store, scooters arrive unassembled in boxes. To assemble a scooter, the following tasks must be performed:
Task 1. | Remove parts from the box. |
Task 2. | Attach wheels to the footboard. |
Task 3. | Attach vertical housing. |
Task 4. | Attach handlebars to vertical housing. |
Task 5. | Put on reflector tape. |
Task 6. | Attach bell to handlebars. |
Task 7. | Attach decals. |
Task 8. | Attach kickstand. |
Task 9. | Attach safety instructions to handlebars. |
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.
83.
Drawings can vary. Possible renderings include the following:
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?
85.
The number of passwords can be found by performing the following multiplication: (26)(26)(26)(25)(3)(9)(8)(7).
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.
87.
The edges are added to the minimum-cost spanning tree in this order: GF, JD, IH, KL, HK, IC, JL, Fl, LE, AI, AB.