Re: Re: Possible bug in HamiltonianCycle

*To*: mathgroup at smc.vnet.net*Subject*: [mg83723] Re: [mg83688] Re: Possible bug in HamiltonianCycle*From*: Murray Eisenberg <murray at math.umass.edu>*Date*: Thu, 29 Nov 2007 06:20:48 -0500 (EST)*Organization*: Mathematics & Statistics, Univ. of Mass./Amherst*References*: <200711240910.EAA17540@smc.vnet.net> <figu6k$fgb$1@smc.vnet.net> <200711281036.FAA17976@smc.vnet.net>*Reply-to*: murray at math.umass.edu

Oops, I missed that the problem was this non-existent edge! Steve Luttrell wrote: > As you say, a Hamiltonian cycle visits each vertex exactly once and returns > to its starting point, but it has to do so by traversing only the edges > defined in the graph. The directed graph example I gave violates this > edge-traversal condition at the last step of the cycle, because the edge > {8,1} does not exist. > > In a separate email Daniel Lichtblau diagnosed the source of this error as > being the dependence of HamiltonianCycle on the function BiconnectedQ which > uses the underlying UNdirected graph. > > I have been in contact with the author of the Combinatorica package, who > agrees that it would be desirable for HamiltonianCycle to handle directed > graphs correctly, and I understand that this is now on to "to do" list. > > Steve Luttrell > West Malvern, UK > > "Murray Eisenberg" <murray at math.umass.edu> wrote in message > news:figu6k$fgb$1 at smc.vnet.net... >> It looks to me like Mathematica did indeed return a Hamiltonian CYCLE: >> it visits each vertex exactly once except that it ends at the same >> vertex where it began (and it traverses the directed graph consistent >> with the directions of edges). >> >> Perhaps you want HamiltonianPath? This does give you all 1's from your >> final Map... expression. >> >> >> Steve Luttrell wrote: >>> 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 >>> >>> >> -- >> Murray Eisenberg murray at math.umass.edu >> Mathematics & Statistics Dept. >> Lederle Graduate Research Tower phone 413 549-1020 (H) >> University of Massachusetts 413 545-2859 (W) >> 710 North Pleasant Street fax 413 545-1801 >> Amherst, MA 01003-9305 >> > > -- Murray Eisenberg murray at math.umass.edu Mathematics & Statistics Dept. Lederle Graduate Research Tower phone 413 549-1020 (H) University of Massachusetts 413 545-2859 (W) 710 North Pleasant Street fax 413 545-1801 Amherst, MA 01003-9305

**References**:**Possible bug in HamiltonianCycle***From:*"Steve Luttrell" <steve@_removemefirst_luttrell.org.uk>

**Re: Possible bug in HamiltonianCycle***From:*"Steve Luttrell" <steve@_removemefirst_luttrell.org.uk>