Re: Possible bug in HamiltonianCycle
- To: mathgroup at smc.vnet.net
- Subject: [mg83688] Re: Possible bug in HamiltonianCycle
- From: "Steve Luttrell" <steve at _removemefirst_luttrell.org.uk>
- Date: Wed, 28 Nov 2007 05:36:38 -0500 (EST)
- References: <200711240910.EAA17540@smc.vnet.net> <figu6k$fgb$1@smc.vnet.net>
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 >
- Follow-Ups:
- Re: Re: Possible bug in HamiltonianCycle
- From: Murray Eisenberg <murray@math.umass.edu>
- Re: Re: Possible bug in HamiltonianCycle
- References:
- Possible bug in HamiltonianCycle
- From: "Steve Luttrell" <steve@_removemefirst_luttrell.org.uk>
- Possible bug in HamiltonianCycle