MATLAB Examples

Finding and displaying Hamiltonian cycles in Matgraph

We illustrate how to find a Hamiltonian cycle in a graph, convert that cycle into a subgraph, and then display the results.

Contents

Create a graph and find a Hamiltonian cycle

For this illustration, we use the dodecahedron graph.

Note: The dodecahedron graph comes with a built-in embedding. We use this embedding later when we draw the graph and its Hamiltonian cycle.

g = graph;
dodecahedron(g);
c = hamiltonian_cycle(g);
disp(c')
  Columns 1 through 14 

     1     2     3     4     5    10    14     9    13     8    12     7    11    16

  Columns 15 through 20 

    17    18    19    20    15     6

Convert the list of vertices into a cycle graph

n = nv(g);
h = graph(n);
for k=1:n-1
	add(h,c(k),c(k+1))
end
add(h,c(1),c(n))

Copy the embedding of the original graph to the cycle

embed(h, getxy(g))

Create the drawing

We first draw g with dotted lines and then overlay the result with h drawn with solid lines.

draw(g,':')
draw(h)

Release graphs

free(g)
free(h)