PVR numbering scheme not solution to all woes : film at 11

On a whim, I decided to try generating all adjacency matrices with the property that they are PVR numbered. The short summary of that link is that a matrix can be expressed as a sequence of positive integers by considering each row of the matrix as a binary number.

The point of doing this (I thought) was that you can number a molecule in such a way that the adjacency matrix is PVR-numbered, and that this is canonical. So my cunning plan was to generate all sequences of n numbers that are partially ordered, choosing them from [1, 2n] to give all non-redundant (simple) graphs with n vertices.

Unfortunately, it seems like this can't work:

This image shows all adjacency matrices for n = 3 which are PVR-numbered. They are made by backtracking through all sequences of integers with a partial order, pruning the solutions using the symmetry of the matrix as a constraint.

Anyway, the point is that the first two graphs are clearly isomorphic! More simply, they both represent propane. Maybe this is well known, but it's a surprise to me...


The method used by the previous deterministic structure generator used a similar approach... If just looking at rows may not be enough... what happens if you would look at the ordering of the columns too?
Anonymous said…
What a great web log. I spend hours on the net reading blogs, about tons of various subjects. I have to first of all give praise to whoever created your theme and second of all to you for writing what i can only describe as an fabulous article. I honestly believe there is a skill to writing articles that only very few posses and honestly you got it. The combining of demonstrative and upper-class content is by all odds super rare with the astronomic amount of blogs on the cyberspace.