Cody

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

No one has attempted to solve this problem yet. Be the first!

Problem Recent Solvers0

No solvers yet, be the first player to solve this problem.

Suggested Problems

More from this Author9

Problem Tags