Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Possible bug in HamiltonianCycle

• To: mathgroup at smc.vnet.net
• Subject: [mg83597] Possible bug in HamiltonianCycle
• From: "Steve Luttrell" <steve at _removemefirst_luttrell.org.uk>
• Date: Sat, 24 Nov 2007 04:10:54 -0500 (EST)

I have applied HamiltonianCycle to various graphs, but seem to have been
obtaining inconsistent results. Here is an example of what I mean:

In[1]:= Needs["Combinatorica`"]

Define a graph adjacency matrix.
In[2]:=
adj={{0,0,0,0,0,0,1,1,0,0,0,0},{0,0,1,0,0,0,0,0,1,1,1,0},{0,0,0,0,0,0,0,0,1,1,1,0},{0,0,1,0,0,0,0,0,1,1,1,0},{1,0,0,0,0,0,1,1,0,0,0,0},{0,1,0,1,1,0,0,0,0,0,0,0},{0,1,0,1,1,1,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0,0,0,1},{0,1,0,1,1,1,0,0,0,0,0,0},{0,0,1,0,0,0,0,0,1,1,0,0},{0,1,0,1,1,1,0,0,0,0,0,0}};

Define the corresponding directed graph.
In[3]:= g=FromAdjacencyMatrix[adj,Type->Directed]
Out[3]= \[SkeletonIndicator]Graph:<36,12,Directed>\[SkeletonIndicator]

Verify that the original adjacency matrix can be recovered.
In[4]:= ToAdjacencyMatrix[g]==adj
Out[4]= True

Compute a Hamiltonian cycle in this graph.
In[5]:= h=HamiltonianCycle[g]
Out[5]= {1,7,2,3,9,12,4,11,10,6,5,8,1}

Break the cycle into its individual edges.
In[6]:= p=Partition[h,2,1]
Out[6]=
{{1,7},{7,2},{2,3},{3,9},{9,12},{12,4},{4,11},{11,10},{10,6},{6,5},{5,8},{8,1}}

Display the adjacency matrix entry corresponding to each of these edges.
In[7]:= Map[Part[adj,Apply[Sequence,#]]&,p]
Out[7]= {1,1,1,1,1,1,1,1,1,1,1,0}

This is where the problem lies, because all these matrix elements should be
1 in a Hamiltonian cycle.

Have I missed something obvious, or is this a bug?

Steve Luttrell
West Malvern, UK 

• Follow-Ups:
  • Re: Possible bug in HamiltonianCycle
    • From: Murray Eisenberg <murray@math.umass.edu>