THE TRAVELING SALESPERSON PROBLEM

OBSERVE:

Before we can formulate the Traveling Salesperson problem, we need to look further into the topic of cycles. Recall that a cycle is a path in which the first and last vertices are the same and there are no repeated edges. The term applies to both directed and undirected graphs -- in a directed graph, the arrows must all go in the same direction. By extension, we can talk about cycles in a network or undirected network. For example, consider the following network:

The cycle A, B, C, A has a total weight of 20 + 7 + 10 = 37. Any cycle with the same edges will have the same total weight. For example, C, A, B, C has a total weight of 37.

So to obtain a cycle with given vertices, we can choose the first vertex arbitrarily.

For the rest of this lab, we will be interested in cycles that include all of the vertices in a network (or undirected network). For example, consider the following undirected network:

The cycle

    A, B, C, D, A

has a total weight of

   6 + 4 + 9 + 5 = 24

There are other cycles with lower total weight.