[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
>
Prev by Date:
**Re: FindInstance puzzler**
Next by Date:
**Derivative of function with indexed variables**
Previous by thread:
**Re: Possible bug in HamiltonianCycle**
Next by thread:
**Re: Re: Possible bug in HamiltonianCycle**
| |