Select a cycle type to start!
Vertices: 6
Edges: 0
Degree sequence: -
• Visits each vertex exactly once
• Returns to starting vertex
• NP-complete problem
• Traverses each edge exactly once
• Returns to starting vertex
• Exists if all vertices have even degree
• Shortest Hamiltonian cycle
• Minimizes total edge weight
• NP-hard optimization problem
A Hamiltonian cycle visits every vertex exactly once and returns to the starting vertex.
Properties:
Necessary conditions:
For a graph to have a Hamiltonian cycle, it must be connected and typically needs high vertex connectivity.
An Eulerian cycle traverses every edge exactly once and returns to the starting vertex.
Euler's Theorem:
A connected graph has an Eulerian cycle if and only if every vertex has even degree.
Algorithm:
Hierholzer's algorithm can find an Eulerian cycle in O(E) time when one exists.
The Traveling Salesperson Problem finds the shortest Hamiltonian cycle.
Optimization:
Among all Hamiltonian cycles, find the one with minimum total weight.
Complexity:
NP-hard problem. Approximation algorithms and heuristics are used for large instances.