Services & ResourcesWolfram ForumsMathGroup Archive

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

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>

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