MathGroup Archive 2005

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

Search the Archive

Re: Hamiltoncircuits on polyhedra

  • To: mathgroup at smc.vnet.net
  • Subject: [mg60455] Re: [mg60399] Hamiltoncircuits on polyhedra
  • From: Andrzej Kozlowski <andrzej at yhc.att.ne.jp>
  • Date: Fri, 16 Sep 2005 03:51:10 -0400 (EDT)
  • References: <200509150916.FAA15840@smc.vnet.net>
  • Reply-to: Andrzej Kozlowski <andrzej at akikoz.net>
  • Sender: owner-wri-mathgroup at wolfram.com

You mean the standard add-on package "DiscreteMath`Combinatorica".  
Indeed, this package has the function HamiltonianCycle, which finds  
hamiltonian cycles on graphs. The package Combinatorica already  
contains graph representations of the regular polyhedra, so it is  
easy to find HamiltonianCycles on, say Dodecahedron:


HamiltonianCycle[DodecahedralGraph]


{1,2,3,4,5,10,12,17,16,20,19,18,13,9,14,8,15,7,11,6,1}

This is very fast. You can also try to find all Hamiltonian cycles using

HamiltonianCycle[DodecahedralGraph,All]

but this will take much longer (remember that the problem of finding  
Hamiltionian cycles is NP complete).

If you want to look for Hamiltonian cycles on non-regular polyhedra,  
e.g. uniform polyhedra, then you will need either to provide graph  
representation yourself (e.g. in the form of adjacency matrices and  
then use the Combinatorica function FromAdjacencyMatrix to construct  
ta graph) or you can find such representations in the package   
UniformPolyhedra.m by Roman Maeder that appeared originally in The  
Mathematica Journal, June 1993 and was reproduced in a modified form  
in the electronic supplement to  the book The Mathematica Programmer II.

Andrzej Kozlowski






On 15 Sep 2005, at 18:16, Jan Lucassen wrote:

> Dear Forum,
>
> Fred Simons (emeritus professor of Technical University Eindhoven)  
> has given me your email adress.
> I should like to know whether Mathematica contains software to  
> determine Hamiltonian circuits on polyhedrs.
> I am not well informed, but I heard about the existence of so  
> called Mathematica commands for the determination of Hamilton
> circuits if it, Mathematica, has at its disposal the package  
> 'Combinatorics'.
>
> Awaiting your answer, yours cordially .
>
> Jan B.M. Lucassen
> Madernolaan 4
> 5624 KT   EINDHOVEN
> tel.: 040 - 243 40 58
>
> e-mail: jan.lucassen at planet.nl
>
>
>


  • Prev by Date: Re: Re: operators for relations in sets
  • Next by Date: Re: Bug in Reduce?
  • Previous by thread: Hamiltoncircuits on polyhedra
  • Next by thread: Re: Hamiltoncircuits on polyhedra