MathGroup Archive 2007

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

Search the Archive

Possible bug in HamiltonianCycle

  • To: mathgroup at
  • Subject: [mg83597] Possible bug in HamiltonianCycle
  • From: "Steve Luttrell" <steve at>
  • 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.

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]

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 

  • Prev by Date: Re: Dynamic Timeout
  • Next by Date: Re: Contour Lines
  • Previous by thread: Re: Contour Lines
  • Next by thread: Re: Possible bug in HamiltonianCycle