All the terminology devoloped to analyze Euler circuits is still important here.

In addition, we define a new type of circuit:

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 a HAMILTON CIRCUIT.

Complete Graph
A graph in which every vertex is joined to every other vertex by exactly one edge is called a COMPLETE GRAPH.

Weighted Graph
A graph in which each edge is "weighted" is called a WEIGHTED GRAPH. A "weight" is a number which might represent a distance, a cost, or some other quantity.

Weight of a Path
The weight of a path (or circuit) is the sum of the weights of each edge in the path (or circuit).

Optimal Hamilton Circuit
An optimal Hamilton Circuit of a graph is one with the smallest possible weight. There can be more than one.

Traveling Salesman Problem
The problem of finding an optimal Hamilton Circuit in a complete weighted graph is often called the Traveling Salesman Problem, or TSP for short.

Back