Hamiltonian Path

From Math Images

Jump to: navigation, search
Image:inprogress.png
Hamiltonian Path
Field: Graph Theory
Created By: Claudio Rocchini
Website: [ http://en.wikipedia.org/wiki/User:Rocchini]

Hamiltonian Path

A Hamiltonian path is a path that visits every vertex once.


Contents

Basic Description

At its very basis, a Hamiltonian Path is a path along a graph that will visit each vertex (also referred to as a node) exactly once. If a Hamiltonian Path can be created for a graph, then it is determined to be a traceable graph.

Also derived from Hamiltonian Paths are Hamiltonian Cycles, also known as Hamiltonian Circuits, which follow the same rules, along with the additional rule that the path must return to the node that it began at on the graph. There is no specific characterization of a Hamiltonian Path -- although there is a list of sufficient conditions that they must meet. If a graph has a Hamiltonian Cycle, then it is determined to be a Hamiltonian Graph [1].

A More Mathematical Explanation

Theorems

<span class="_togglegroup _toggle_initshow _toggle _toggler toggle-visible" style="dis [...]

Theorems

Bondy-Chvátal Theorem

Also simply referred to as Chvátal's Theorem. First, consider the vertex degrees on a graph obeying the following pattern of d1 ≤... ≤ dm in which each successive degree angle along the points on the path are equal to or less than the following degree angle. If either of the following cases is true, then the graph in consideration is Hamiltonian (so long as i < n/2) [2]:

  • di ≥ i+1
  • dn-i ≥ n-i

Dirac's Theorem

A simple graph with n ≥ 3 vertices has a Hamiltonian Cycles so long as the degree at each vertex is ≥ n/2 or greater than half the number of vertices present in the graph [3].

Ore's Theorem

In a graph with at least three vertices such that every pair of the n graph vertices which are not joined by an graph edge has a sum of valences [4] which is >=n, then G is Hamiltonian [5].

Ghouila-Houiri's Theorem

When addressing a strongly connected simple directed graph and considering (p) as the number of vertices on the graph, if the inner degree at the vertex is ≥ p/2 and the outer degree at the vertex is ≥ p/2 for all vertices v in the graph, then the graph has a Hamiltonian cycle. [6]

Determining Hamiltonian Cycles

The Traveling Salesman Problem was created as a (cont...)

NP Completeness Proof

(add here)

Other Hamiltonian

Image:HamiltonianPlatonics.gif Platonic Solids are Hamiltonian, a shown by the image above. [7]




Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.




References

  1. ↑ DeLeon, Melissa, "A Study of Sufficient Conditions for Hamiltonian Cycles". Department of Mathematics and Computer Science, Seton Hall University.
  2. ↑ Weisstein, Eric W. "Chvátal's Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ChvatalsTheorem.html
  3. ↑ Weisstein, Eric W. "Dirac's Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/DiracsTheorem.html
  4. ↑ Weisstein, Eric W. "Valence." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Valence.html
  5. ↑ Weisstein, Eric W. "Ore's Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/OresTheorem.html
  6. ↑ Notes on sufficient conditions for a graph to be hamiltonian. (1991). Internat. J. Math. & Math. Sci., 14(4), 825-827.
  7. ↑ Weisstein, Eric W. "Hamiltonian Graph." From MathWorld--A Wolfram Web Resource.

Future Directions for this Page

  • Make Theorems more user-friendly to read?
  • A GIF that draws a Hamiltonian Path?
  • There's a good applet here, find the terms of use for it?
  • Create a Traveling Salesman Problem page -- not as a helper page, but a full-fledged page for extended explanation.


If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Retrieved from "http://mathforum.org/mathimages/index.php/Hamiltonian_Path"
Personal tools
Create or Edit a Page