12.9.1: Exercises

For the following exercises, determine whether the algorithm described is a greedy algorithm or a brute force algorithm.

Exercise \(\PageIndex{1}\)

The algorithm for creating graph colorings in the section Navigating Graphs involved coloring the vertex of highest degree first, coloring as many other vertices as possible each color from highest to lowest degree, then repeating this process for the remaining vertices.

Exercise \(\PageIndex{2}\)

Pallets of goods are to be transported on 10 flatbed trucks which have weight limits. To determine which goods will be shipped together, all the possible ways to divide the goods into 10 groups is listed and the total weight of each group is calculated.

Exercise \(\PageIndex{3}\)

A wedding planner is creating a seating arrangement for the reception dinner. The couple has provided a list of which guests must be seated together. The wedding planner prefers to use the fewest tables possible so that there is more space to mingle at the reception. The planner creates a list of all possible seating arrangements and selects one that meets these criteria.

Exercise \(\PageIndex{4}\)

Packages must be loaded into freight cars to be transported by train. It is preferred to use the fewest freight cars possible to keep the costs down. As each freight car is packed, the package with the largest girth that will fit in the freight car is loaded and this is repeated until the freight car can hold no more packages. When a freight car can hold no more packages, the next freight car is loaded.

For the following exercises, use the figure to calculate the number of distinct Hamilton cycles beginning at the given vertex in the given graph. How many of those could possibly result in a different weight?

Exercise \(\PageIndex{5}\)

Graph A, vertex a

Exercise \(\PageIndex{6}\)

Graph B, vertex e

Exercise \(\PageIndex{7}\)

Graph C, vertex k

Exercise \(\PageIndex{8}\)

Graph D, vertex o

For the following exercises, use the figure to list all the distinct Hamilton cycles beginning at the given vertex in the given graph. Indicate which pairs of Hamilton cycles are reverses of each other.

Exercise \(\PageIndex{9}\)

Graph A, vertex a

Exercise \(\PageIndex{10}\)

Graph B, vertex e

Exercise \(\PageIndex{11}\)

Graph C, vertex k

Exercise \(\PageIndex{12}\)

Graph D, vertex o

For the following exercises, use the figure to find a Hamilton cycle of least weight for the given graph, beginning at the given vertex, and using the brute force method. What is the weight of the cycle?

Exercise \(\PageIndex{13}\)

Graph A, vertex a

Exercise \(\PageIndex{14}\)

Graph B, vertex e

Exercise \(\PageIndex{15}\)

Graph C, vertex k

Exercise \(\PageIndex{16}\)

Graph D, vertex o

For the following exercises, use the figure to find a Hamilton cycle of low weight for the given graph, beginning at the given vertex, and using the nearest neighbor method. What is the weight of the cycle?

Exercise \(\PageIndex{17}\)

Graph A, vertex a

Exercise \(\PageIndex{18}\)

Graph B, vertex e

Exercise \(\PageIndex{19}\)

Graph C, vertex k

Exercise \(\PageIndex{20}\)

Graph D, vertex o

For the following exercises, use your solutions to Exercises 13–20 to compare the results of the brute force method to the results of the nearest neighbor method for each graph. Indicate whether the Hamilton cycle was the same or different and whether the weights were the same or different. If the weights are different, indicate which method gave the lower weight. Are your observations consistent with the characteristics of brute force algorithms and greedy algorithms? Explain your reasoning.

Exercise \(\PageIndex{21}\)

Graph A, vertex a

Exercise \(\PageIndex{22}\)

Graph B, vertex e

Exercise \(\PageIndex{23}\)

Graph C, vertex k

Exercise \(\PageIndex{24}\)

Graph D, vertex o

For the following exercises, use the table to create a complete weighted graph in which the vertices are the given cities, and the weights are the distances between them.

Cities	U	V	W	X	Y	Z
U	0	89	37	49	54	28
V	89	0	76	68	92	112
W	37	76	0	45	52	49
X	49	68	45	0	66	47
Y	54	92	52	66	0	29
Z	28	112	49	47	29	0

Distances between Cities U, V, W, X, Y, and Z in kilometers

Exercise \(\PageIndex{25}\)

U, V, W, X

Exercise \(\PageIndex{26}\)

U, W, Y, Z

Exercise \(\PageIndex{27}\)

U, X, Y, Z

Exercise \(\PageIndex{28}\)

U, V, W, X, Y

Exercise \(\PageIndex{29}\)

U, W, X, Y, Z

Exercise \(\PageIndex{30}\)

U, V, W, X, Y, Z

For the following exercises, use your solutions to Exercises 25–30 and the nearest neighbor method to find a Hamilton cycle to solve the traveling salesperson problem of finding a reasonably short route to leave from city U, visit each of the other cities listed and return to city U. Indicate the distance required to travel the route you found.

Exercise \(\PageIndex{31}\)

U, V, W, X

Exercise \(\PageIndex{32}\)

U, W, Y, Z

Exercise \(\PageIndex{33}\)

U, X, Y, Z

Exercise \(\PageIndex{34}\)

U, V, W, X, Y

Exercise \(\PageIndex{35}\)

U, W, X, Y, Z

Exercise \(\PageIndex{36}\)

U, V, W, X, Y, Z

For the following exercises, use your solutions to Exercises 25–30 and the brute force method to find a Hamilton cycle of lowest weight to solve the traveling salesperson problem of finding a shortest route to leave from city U, visit each of the other cities listed and return to city U. Indicate the distance required to travel the route you found.

Exercise \(\PageIndex{37}\)

U, V, W, X

Exercise \(\PageIndex{38}\)

U, W, Y, Z

Exercise \(\PageIndex{39}\)

U, X, Y, Z

Exercise \(\PageIndex{40}\)

U, V, W, X, Y

Exercise \(\PageIndex{41}\)

U, W, X, Y, Z

For the following exercises, use your solutions to the indicated exercises to compare the results of the brute force method to the results of the nearest neighbor method for each traveling salesman problem of finding a reasonably short route to leave from city U, visit each of the other cities listed and return to city U. Indicate whether the greedy algorithm resulted in a Hamilton cycle of the same weight, lower weight, or higher weight. Is this consistent with the characteristics of brute force algorithms and greedy algorithms? Explain your reasoning

Exercise \(\PageIndex{42}\)

Exercises 32 and 38: U, W, Y, Z

Exercise \(\PageIndex{43}\)

Exercises 31 and 37: U, V, W, X

Exercise \(\PageIndex{44}\)

Exercises 34 and 40: U, V, W, X, Y

Exercise \(\PageIndex{45}\)

Exercises 35 and 41: U, W, X, Y, Z

Exercise \(\PageIndex{46}\)

Exercises 33 and 39: U, X, Y, Z

The products at a particular factory are manufactured in phases. The same equipment is utilized for each phase, but it must be formatted differently to accomplish different tasks. The transition time to convert between a format for one task and another task varies. The times are given in Table 12.13. In the following exercises, use the table and the nearest neighbor method to find an order in which to complete the tasks, which keeps the transition times down and ends with the same set up as it began so that the factory is ready to start the next batch. Assume that there are no restrictions on which tasks can be completed in which order. Hint: The nearest neighbor algorithm may give a different result depending on which vertex is the starting vertex, so, you must check all possibilities.

Task	A	B	C	D	E	F	G
A	0	75	130	45	120	70	100
B	75	0	140	65	115	25	60
C	130	140	0	35	55	20	125
D	45	65	35	0	50	30	40
E	120	115	55	50	0	95	145
F	70	25	20	30	95	0	15
G	100	60	125	40	145	15	0

Manufacturing Equipment Transition Times in Minutes

Exercise \(\PageIndex{47}\)

A, C, D, F, G

Exercise \(\PageIndex{48}\)

B, D, E, F, G

Exercise \(\PageIndex{49}\)

A, B, C, D, E, F

Exercise \(\PageIndex{50}\)

B, C, D, E, F, G

Exercise \(\PageIndex{51}\)

A, B, C, D, E, F, G

---