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
-
288 Solvers
-
Back to basics 9 - Indexed References
439 Solvers
-
Back to basics 11 - Max Integer
780 Solvers
-
52 Solvers
-
Sum the entries of each column of a matrix which satisfy a logical condition.
160 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!