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
>
>
>
- References:
- Hamiltoncircuits on polyhedra
- From: Jan Lucassen <jan.lucassen@planet.nl>
- Hamiltoncircuits on polyhedra