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>
- Re: Possible bug in HamiltonianCycle