Problem

Use the brute force algorithm to find a Hamilton circuit that has minimal weight. Recall t...

Use the brute force algorithm to find a Hamilton circuit that has minimal weight. Recall that we found all Hamilton circuits in K4 in Example.

Finding Hamilton Circuits in K4.

Find all Hamilton circuits in K4.

SOLUTION:

Path ABCDA shown in Figure is one of the Hamilton circuits in K4. We will consider path BCDAB to be the same path because it passes through the same vertices in the same order and the only difference is that we are beginning and ending at vertex B rather than vertex A. In light of this remark, we will assume that all Hamilton circuits in this example begin at vertex A.

A good drawing can put us on the right track in understanding this problem and finding a solution. Realize that in constructing a Hamilton circuit in K4, you have to decide on a first vertex, then a second, then a third, and so on. This sequence of decisions can be visualized in the tree diagram in Figure. Begin at vertex A, then go to either B, C, or D. If we decide to go to B, we can then choose either C or D, and so on. The red path, highlighted in Figure, shows how to construct the Hamilton path ACBD and then, by returning to A, get the Hamilton circuit ACBDA.

Finding Hamilton circuits in K4