Re: Possible bug in HamiltonianCycle
- To: mathgroup at smc.vnet.net
- Subject: [mg83644] Re: [mg83597] Possible bug in HamiltonianCycle
- From: Murray Eisenberg <murray at math.umass.edu>
- Date: Tue, 27 Nov 2007 06:09:41 -0500 (EST)
- Organization: Mathematics & Statistics, Univ. of Mass./Amherst
- References: <200711240910.EAA17540@smc.vnet.net>
- Reply-to: murray at math.umass.edu
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
- References:
- Possible bug in HamiltonianCycle
- From: "Steve Luttrell" <steve@_removemefirst_luttrell.org.uk>
- Possible bug in HamiltonianCycle