Consider the following road map
The explorer's Problem: An explorer wants to explore all the routes between a number of cities. Can a tour be found which traverses each route only once? Particularly, find a tour which starts at A, goes along each road exactly once, and ends back at A.
Examples of such tour are
The Explorer travels along each road (edges) just once but may visit a particular city (vertex) several times.
The Traveler's Problem
A traveler wants to visit a number of cities. Can a tour be found which visits each city only once? Particularly, find a tour which starts at A, goes to each city exactly once, and ends back at A.
Examples of such tour are
The travelers visits each city (vertex) just once but may omit several of the roads (edges) on the way.
A connected graph G is Eulerian if there is a closed trail which includes every edge of G, such a trail is called an Eulerian trail.
A connected graph G is Hamiltonian if there is a cycle which includes every vertex of G; such a cycle is called a Hamiltonian cycle.
Consider the following examples:
This graph is BOTH Eulerian and Hamiltonian.
This graph is Eulerian, but NOT Hamiltonian.
This graph is an Hamiltionian, but NOT Eulerian.
This graph is NEITHER Eulerian NOR Hamiltionian
Theorem Let G be a connected graph. Then G is Eulerian if and only if every vertex of G has even degree.
- If G is Eulerian, then every vertex of G has even degree.
- If every vertex of G has even degree, then G is Eulerian.
- Edge-traceable graphs.
- Diagrams-Tracing Puzzles.
- Mazes and labyrinths,
- The Chinese Postman Problem.
- The Rotating Drum Problem.
Neither necessary nor sufficient condition is known for a graph to be Hamiltonian. The search for necessary or sufficient conditions is a major area of study in graph theory today.
Dirac's Theorem Let G be a simple graph with n vertices where n ≥ 3 If deg(v) ≥ 1/2 n for each vertex v, then G is Hamiltonian.
n = 6 and deg(v) = 3 for each vertex, so this graph is Hamiltonian by Dirac's theorem.
Ore's Theorem Let G be a simple graph with n vertices where n ≥ 2 if deg(v) + deg(w) ≥ n for each pair of non-adjacent vertices v and w, then G is Hamiltonian.
n = 5 but deg(u) = 2, so Dirac's theorem does not apply. However, deg(v) + deg(w) ≥ 5 for all pairs of vertices v and w (infact, for all pairs of vertices v and w), so this graph is Hamiltonian by Ore's theorem.
Note that if deg(v) ≥ 1/2 n for each vertex, then deg(v) + deg(w) ≥ n for each pair of vertices v and w. It follows that Dirac's theorem can be deduced from Ore's theorem, so we prove only Ore's threoem.
Hamiltonain - Type Problem
- Gray Codes.
- The Traveling Salesperson Problem
- Ranking in Tournaments.