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
-
Extract leading non-zero digit
2116 Solvers
-
Count from 0 to N^M in base N.
235 Solvers
-
Given an unsigned integer x, find the largest y by rearranging the bits in x
1791 Solvers
-
17 Solvers
-
Solve the set of simultaneous linear equations
409 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!