Editing HamiltonCycle
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
If you want a password, email topicsinmaths@solipsys.co.uk
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Fri Mar 29 02:46:25 2024.
Press
to finish editing.
Who can edit this page?
World editing disabled
Members
Council
Admin
[[[>50 The decision problem: * Does this graph have a Hamilton Cycle? is NP-Complete. That means that there is no known efficient procedure to decide whether or not a given graph has a Hamilton Cycle. It's worth noting that given a solution to the Decision version of the Hamilton Cycle problem, we can, with only a polynomial amount of extra work, find an actual Hamilton cycle. ]]] Informally, a Hamilton Cycle in a graph is a cycle that visits every vertex exactly once. Because it's a cycle it finishes where it started. Slightly more formally, a Hamilton Cycle is a list of vertices from the graph such that: * Each vertex appear exactly once * For every $1{\le}i{\lt}n,$ $(v_i,v_{i+1})\in{E(G)}$ ** where we take $v_{n+1}=v_1$ For a given graph it's usually easy to find a Hamilton cycle, or easy to show that there is no Hamilton Cycle, but the problem of finding a Hamilton Cycle in a general or arbitrary graph has no known efficient procedure. It is NP-Complete.