On Fri, Nov 15, 2013 at 08:48:19PM +0100, John Colvin wrote: > On Friday, 15 November 2013 at 18:43:12 UTC, H. S. Teoh wrote: > >so the edges of the graph may be thought of as a subset of the > >edges of an n-dimensional grid. > > Could perhaps elaborate on this point? > > As far as I can see, the possible values of the nodes are all the > points in N^n (or Z^n, dunno whether you have negatives) and the > edges are all in the set of i*e_j for i in Z and j in N, where e_j > is the unit vector along one axis, i.e. the edges are the euclidean > basis vectors and their negatives.
Actually, i can only be 1 or -1. > How is this the same as the edges of an n-dimensional grid? Basically, adjacent nodes differ only in a single coordinate, and that difference can only be 1 or -1. So for the 2D case, if you graph the nodes on the plane, the edges would be horizontal/vertical line segments of unit length. If you consider the 2D grid's edges to be *all* possible such line segments, then in that sense you could think of the graph's edges as being a subset of the 2D grid's. I was hoping that this fact can be taken advantage of, to make a compact representation of visited nodes. T -- By understanding a machine-oriented language, the programmer will tend to use a much more efficient method; it is much closer to reality. -- D. Knuth
