Euler circuits/paths are not the appropriate tool for analyzing problems where it is only important to visit each vertex. For problems of this type, whether or not an edge is traveled is not important. (Euler circuits/paths deal with situations where it is important to travel every edge.)
Hamilton Circuit
A circuit that starts at a vertex of a graph, passes through every vertex exactly once,
and returns to the starting vertex is called a HAMILTON CIRCUIT.
Unfortunately, there are no counterparts to Euler’s theorems that tell us whether or not a graph has a Hamilton Circuit.
Occasionally, there are situations where the following theorem will help us determine that a graph does have a Hamilton Circuit.
Dirac’s Theorem
If each vertex of a connected graph with 3 or more vertices is adjacent to at least half
of the remaining vertices, then the graph has a Hamilton Circuit. Two vertices are
ADJACENT if there is an edge connecting them.
Complete Graph
A graph in which every vertex is joined to every other vertex by exactly one edge
is called a COMPLETE GRAPH.
- Complete graphs have LOTS of Hamilton Circuits!
- In a complete graph with N vertices, each vertex has degree N-1.
- The total number of edges in a complete graph with N vertices is N(N-1)/2.
- A complete graph with N vertices has (N-1)! Hamilton circuits. Half of these are just exact reversals of the other half. When we don’t want to count exact reversals, we will use the term distinct. So, a complete graph with N vertices has (N-1)! / 2 distinct Hamilton circuits.
In problems involving Hamilton Circuits, there are often many seemingly equivalent routes. The most important class of problems solved via Hamilton Circuits is actually when the edges connecting vertices have different weights. (For instance, it might be less expensive to travel one edge rather than a different one or perhaps the distance traveled is less.)
Weighted Graph
A graph in which each edge is "weighted" is called a WEIGHTED GRAPH.
The weight of a path (or circuit) is the sum of the weights of each edge in the path (or circuit).
An optimal Hamilton Circuit is one with the smallest possible weight. There may be more than one!
The Traveling Salesman Problem (TSP)
The problem of finding an optimal Hamilton Circuit in a complete weighted graph is
often called the Traveling Salesman Problem (TSP).
We will discuss several methods of ‘solving" TSPs.
The Traveling Salesman Problem (TSP): Solution
Methods (Algorithms)
The problem of finding an optimal Hamilton Circuit in a complete weighted graph is
often called the Traveling Salesman Problem (TSP).
We will discuss several methods of ‘solving" TSPs.
THE BRUTE FORCE ALGORITHM
- List all possible Hamilton circuits (leaving out the exact reversals, if you wish)
- Find the weight of each
- Choose (the) one with the smallest weight.
Pluses: It always works (given enough time & care).
Minuses: It can only be used for relatively small graphs. For a computer doing 10,000 circuits/sec, it would take about 18 seconds to handle 10 vertices, 50 days to handle 15 vertices, 2 years for 16 vertices, 193,000 years for 20 vertices.
Bottom line: Unfortunately, the Brute Force Algorithm is the ONLY method known that is guaranteed to produce an optimal solution.
Mathematicians have not been able to prove that another such method exists nor have they been able to prove that one doesn’t exist.
This is one of the most important and famous unsolved problems in mathematics. If you can find an efficient solution to the TSP, you will be rich and famous!!
Although we do not have an efficient algorithm for solving TSPs, we do have several algorithms that produce results that may not be optimal; in this respect, we are willing to give up our requirement for an optimal solution in the interest of time and settle for a "good" solution which may not be optimal. We call this class of algorithms approximate algorithms. The remaining algorithms are approximate algorithms.
Approximate Algorithms (for solving TSPs)
For approximate algorithms, we will be interested in a quantity called the relative error.
We will only be asked to calculate the Relative Error in simple cases.
RELATIVE ERROR will primarily be important to us for theoretical reasons since we will be able to calculate the Optimal Solution only for simple cases. A complete discussion of evaluating the performance of an approximate algorithm is beyond the scope of this course BUT, two factors which are important are: (1) worst-case performance and (2) average performance.
The relative error tells us how close the approximate solution is to the optimal solution.
CHEAPEST LINK ALGORITHM (CLA)
- Choose the edge with the smallest weight (the "cheapest" edge), randomly breaking ties
- Keep choosing the "cheapest" edge unless it (a) closes a smaller circuit OR (b) results in 3 selected edges coming out of a single vertex
- Continue until the Hamilton Circuit is complete
The resulting path is a Hamilton Circuit.
NEAREST NEIGHBOR ALGORITHM (NNA)
- Start at a vertex (think of it as your Home city)
- Travel to the vertex (think of it as a city) that you haven’t been to yet whose path has the smallest weight (think of it as the closest city) (If there is a tie, pick randomly.)
- Continue until you travel to all vertices (cities)
- Travel back to your starting vertex (your Home)
The resulting path is a Hamilton Circuit.
REPETITIVE NEAREST NEIGHBOR ALGORITHM (RNNA)
- DO NNA for each vertex (city)
- Choose the best solution (smallest weight)
- If necessary, rewrite this solution with a particular starting vertex (Home)
The resulting path is a Hamilton Circuit.