Problem 45382. Find a Hamiltonian Cycle in a Graph
You are given a graph g and asked to find a Hamiltonian cycle of g.
See MATLAB graph documentation for details of the graph data structure.
A cycle of g is a sequence of vertices of g such that each adjacent pair of vertices in the sequence share an edge in g and the first and last vertices in the sequence share an edge in g. A Hamiltonian cycle of g is a cycle of g that visits each vertex of g exactly once.
For example, consider the adjacency matrix below.
A = [ 0 0 0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 1 0 0];
This corresponds to the graph with vertices labeled 1 through 8 and an edge between two vertices i and j if and only if A(i, j) == 1. This graph has cycles of vertices [3 4 8], [3 8 1 4], and [5 1 4 3 8], among others. Try the commands below to visualize this.
g = graph(A); gh = plot(g);
A Hamiltonian cycle for this graph g is [1 5 6 8 3 4 2 7].
For another fun challenge, see: Restricted Addition
Solution Stats
Problem Comments

1 Comment
nice (and difficult) problem! (if possible, please fix the testsuite adding something along the lines of "assert(n==numel(unique(c)))")
Solution Comments
Show commentsProblem Recent Solvers2
Suggested Problems

Find the peak 3n+1 sequence value
2448 Solvers

66 Solvers

Sum of diagonal of a square matrix
1558 Solvers

Area of an equilateral triangle
5886 Solvers

5939 Solvers
More from this Author9
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!