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
Find a Hamiltonian Cycle in a Graph
0 Solvers
Problem Tags