Project: Edges with Equal Weights

David M. Clark and W. Ted Mahavier

( Chapter 3: W. Ted Mahavier < E.L. May < K.M. Shannon ¹ )

If each of \(X\) and \(Y\) is a person, then the relation \(X < Y\) indicates that the notes originated with \(Y\) and were subsequently modified by \(X\text{,}\) who takes full responsibility for the current version. While \(Y\) is credited with the genesis of the notes, s/he makes no claim to the accuracy of the current version which may or may not reflect her/his original version.

Section Project: Edges with Equal Weights

The weighted graphs presented in this chapter have all had the property that no two edges have the same weight. If, in the application of the greedy algorithms, there is more than one edge with minimal weight, we simply pick one of them at random. This means that we may get different outcomes depending on the choices we make. See how much variation there is in the outcomes when your class does the following problem.

Problem 6.20.

Suppose that you need to make a delivery to each of 11 friends and then return home. What's more, your car is in very bad shape and you don't want to drive it any further than absolutely necessary. Call your house A and the houses of your friends B, C, D, E, F, G, H, I, J, K and L. Table 6.21 below indicates the distances between each pair of houses. You need to find a Hamilton circuit through the complete graph on 12 vertices, A, B, C, D, E, F, G, H, I, J, K and L, which has as small a total distance as possible. According to what you learned in Problem 6.9, you are quite certain that you don't want to use the Brute Force Algorithm to find this circuit.

Table 6.21. table of distances between 12 houses


	A	B	C	D	E	F	G	H	I	J	K	L

A		8	15	7	6	9	10	16	11	7	9	10

B			9	12	6	9	11	15	12	8	9	6

C				7	10	11	9	5	6	9	10	12

D					8	6	13	10	9	5	11	7

E						10	7	6	9	10	8	9

F							9	8	10	6	5	16

G								7	15	7	6	8

H									5	9	14	10

I										8	19	7

J											12	5

K												6

Pick a random Hamilton circuit and compute its total length.
Apply the Nearest Neighbor Greedy Algorithm, starting from A (only), to find a Hamilton circuit. What is its total length?
Apply the Nearest Neighbor Greedy Algorithm, starting from D (only), to find a Hamilton circuit. What is its total length?
Apply the Cheapest Link Greedy Algorithm to find a Hamilton circuit. What is the length of this circuit?

The example in Problem 6.20 shows how the greedy algorithms are normally used. They are the best methods currently available to efficiently compute low weight Hamilton circuits when the Brute Force Algorithm is not feasible to use, as illustrated in Problem 6.9. However, there are instances where they can fail completely.

Problem 6.22.

Construct a weighted graph with 4 vertices and some edges of equal weight such that both greedy algorithms can be used to obtain either a minimum weight Hamilton circuit or a maximum weight Hamilton circuit, depending on the choices made along the way.