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>
- Possible bug in HamiltonianCycle