Efficient solution for finding Hamilton cycles in undirected graphs
Wadee Alhalabi1, Omar Kitanneh2, Amira Alharbi2
1Faculty of Computing and Information Technology, King Abdulaziz University, Jeddah, Saudi Arabia.
Abstract:
The Hamilton cycle problem is closely related to a series of famous problems and puzzles (traveling salesman problem, Icosian game) and, due to the fact that it is NP-complete, it was extensively studied with different algorithms to solve it. The most efficient algorithm is not known. In this paper, a necessary condition for an arbitrary un-directed graph to have Hamilton cycle is proposed. Based on this condition, a mathematical solution for this problem is developed and several proofs and an algorithmic approach are introduced. The algorithm is successfully implemented on many Hamiltonian and non-Hamiltonian graphs. This provides a new effective approach to solve a problem that is fundamental in graph theory and can influence the manner in which the existing applications are used and improved.
Related Concept Videos
Graphs of Equations in Two Variables
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
Entropy Change in Reversible Processes
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
Graphs of Polar Equations
Cyclic Processes And Isolated Systems
In the case of a non-isolated system, the change in the internal energy is zero only if the process is cyclic. A thermodynamic process is considered cyclic if the system undergoes a series of changes and returns to its initial state.
Consider a cyclic process that returns to its initial state, undergoing a four-step process. The heat transfer along each...
Graphs of Functions


