Mathematica 9 is now available
Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2007

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

Search the Archive

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


  • Prev by Date: Re: Trouble saving Version 6 notebook when Juniper SSL VPN is on
  • Next by Date: Re: FindInstance puzzler
  • Previous by thread: Possible bug in HamiltonianCycle
  • Next by thread: Re: Possible bug in HamiltonianCycle