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

40.0% Correct | 60.0% Incorrect
Last Solution submitted on Mar 19, 2023

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers2

Suggested Problems

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!