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