![matthen:
When designing an art gallery, you might want to make it so that people can walk through it visiting each exhibit exactly once returning back to the front door. In the plan on the left, this is possible. In the other plan, it is impossible to visit every dot (exhibit) without revisiting an exhibit. There is no quick method to check a general art gallery to see if it has this property (that it is Hamiltonian) - you just have to check all possible paths. [more] [code]
Actually, sometimes you can notice a simple feature of a graph that ensures it has a Hamiltonian cycle. Two related examples:
Theorem (Ore): Let G be a simple graph on n > 2 vertices. If for every pair of nonadjacent vertices u and v in G we have $$deg(u) + deg(v) \geq n,$$ then G is Hamiltonian.
Theorem (Dirac): Let G be a simple graph on n > 2 vertices. If for every u in V(G) we have $$deg(u) \geq n/2,$$ then G is Hamiltonian.
These are sufficient conditions for a graph to be Hamiltonian, but they are not necessary; there are Hamiltonian graphs that don’t satisfy either of these. Going in the other direction, here’s one necessary condition:
Theorem: If G is a simple Hamiltonian graph, then for each S subset of V(G), the number of components of G - S is at most |S|.
In other words, if throwing away n vertices of G ever breaks G up into more than n pieces, G cannot be Hamiltonian. But there are non-Hamiltonian graphs that have this feature, like the graph on the right in the animation above.
So we don’t have the whole story yet. If you’re looking at a graph which none of the above theorems say anything about, it may be Hamiltonian and you’d be hard pressed to see it without just checking all paths manually. It may be that the Hamiltonian property doesn’t put enough restrictions on the structure of a graph to provide us with complete necessary & sufficient conditions to characterize it. However, if we happen to notice a graph satisfies either of the first two theorems mentioned above, we can actually run an algorithm on it to find a Hamiltonian cycle in a reasonable amount of time.
Apparently a complete solution to this problem would earn its solver $1,000,000, as it is equivalent to the P-vs-NP Millennium Problem.
Source:
Graph Theory: Modeling, Applications, and Algorithms by Agnarsson & Greenlaw, Prentice Hall 2007](http://24.media.tumblr.com/tumblr_lme082yXiB1qfg7o3o1_400.gif)
When designing an art gallery, you might want to make it so that people can walk through it visiting each exhibit exactly once returning back to the front door. In the plan on the left, this is possible. In the other plan, it is impossible to visit every dot (exhibit) without revisiting an exhibit. There is no quick method to check a general art gallery to see if it has this property (that it is Hamiltonian) - you just have to check all possible paths. [more] [code]
Actually, sometimes you can notice a simple feature of a graph that ensures it has a Hamiltonian cycle. Two related examples:
Theorem (Ore): Let G be a simple graph on n > 2 vertices. If for every pair of nonadjacent vertices u and v in G we have $$deg(u) + deg(v) \geq n,$$ then G is Hamiltonian.
Theorem (Dirac): Let G be a simple graph on n > 2 vertices. If for every u in V(G) we have $$deg(u) \geq n/2,$$ then G is Hamiltonian.
These are sufficient conditions for a graph to be Hamiltonian, but they are not necessary; there are Hamiltonian graphs that don’t satisfy either of these. Going in the other direction, here’s one necessary condition:
Theorem: If G is a simple Hamiltonian graph, then for each S subset of V(G), the number of components of G - S is at most |S|.
In other words, if throwing away n vertices of G ever breaks G up into more than n pieces, G cannot be Hamiltonian. But there are non-Hamiltonian graphs that have this feature, like the graph on the right in the animation above.
So we don’t have the whole story yet. If you’re looking at a graph which none of the above theorems say anything about, it may be Hamiltonian and you’d be hard pressed to see it without just checking all paths manually. It may be that the Hamiltonian property doesn’t put enough restrictions on the structure of a graph to provide us with complete necessary & sufficient conditions to characterize it. However, if we happen to notice a graph satisfies either of the first two theorems mentioned above, we can actually run an algorithm on it to find a Hamiltonian cycle in a reasonable amount of time.
Apparently a complete solution to this problem would earn its solver $1,000,000, as it is equivalent to the P-vs-NP Millennium Problem.
Source:
- Graph Theory: Modeling, Applications, and Algorithms by Agnarsson & Greenlaw, Prentice Hall 2007
