Problem 45382. Find a Hamiltonian Cycle in a Graph

Created by Jonathan

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are given a graph g and asked to find a Hamiltonian cycle of g.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>See</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/help/matlab/ref/graph.html\"><w:r><w:t>MATLAB graph documentation</w:t></w:r></w:hyperlink><w:r><w:t> for details of the graph data structure.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example, consider the adjacency matrix below.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[A = [\n 0 0 0 1 1 0 1 1\n 0 1 0 1 0 0 1 0\n 0 0 0 1 1 0 0 1\n 1 1 1 1 0 1 0 1\n 1 0 1 0 0 1 0 1\n 0 0 0 1 1 0 0 1\n 1 1 0 0 0 0 0 0\n 1 0 1 1 1 1 0 0];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[g = graph(A);\ngh = plot(g);]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A Hamiltonian cycle for this graph g is [1 5 6 8 3 4 2 7].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For another fun challenge, see:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/45252-restricted-addition-v1\"><w:r><w:t>Restricted Addition</w:t></w:r></w:hyperlink></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

You are given a graph g and asked to find a Hamiltonian cycle of g.See <a href = "https://www.mathworks.com/help/matlab/ref/graph.html">MATLAB graph documentation</a> 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.<pre class="language-matlab">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];
</pre>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.<pre class="language-matlab">g = graph(A);
gh = plot(g);
</pre>A Hamiltonian cycle for this graph g is [1 5 6 8 3 4 2 7].For another fun challenge, see: <a href = "https://www.mathworks.com/matlabcentral/cody/problems/45252-restricted-addition-v1">Restricted Addition</a>

Solve

Solution Stats

8 Solutions
2 Solvers

Last Solution submitted on Nov 21, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Alfonso Nieto-Castanon on 23 Aug 2020

nice (and difficult) problem! (if possible, please fix the testsuite adding something along the lines of "assert(n==numel(unique(c)))")

Solution Comments

Solution 2871488

1 Comment

1 Comment

Alfonso Nieto-Castanon on 23 Aug 2020

example of invalid solution

Problem Recent Solvers2

Problem Tags

cycle graph hamiltonian

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 45382. Find a Hamiltonian Cycle in a Graph

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers2

Suggested Problems

More from this Author9

Problem Tags

Community Treasure Hunt

Problem 45382. Find a Hamiltonian Cycle in a Graph

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers2

Suggested Problems

More from this Author9

Problem Tags

Community Treasure Hunt

Players