[r-t] # Extents on N bells

[Chris Poole]

On Wed, 18 Aug 2004, Martin Bright wrote:

> There must really be loads - as well as all the extents using sensible
> methods, there will be vastly many more which have no structure, but are
> just seemingly random sequences of changes.
>
> I'd be surprised if there were a good way of working this out.  Given that
> it's very hard to determine whether a general graph _has_ a Hamiltonian
> cycle (i.e. a cycle that visits every vertex precisely once), it must also
> be difficult to count them.  (Otherwise, to tell whether one existed, you
> could just count them and see whether there were more than 0.)

Why not map the nodes to edges (and vice versa).  Then you're looking for
an Eulerian Circuit instead of a Hamiltonian one;  the former are
Mathematically easier.  There's a shed-load of structure to the graph, so
could it be worked out from there?  Details are left to the reader....


Chris