MathGroup Archive 2007

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

Search the Archive

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


  • Prev by Date: Re: FindInstance puzzler
  • Next by Date: Re: optimization routine using conjugate gradient (or other) method?
  • Previous by thread: Re: Possible bug in HamiltonianCycle
  • Next by thread: Re: Possible bug in HamiltonianCycle