Re: New algorithm for the isomorphism of graphs

mimouni gave another trivial example:
G=3D(12 ;24 ;34 ;36 ;45 ;56) and G'=3D(ab ;ae ;bc ;cf ;df ;ef)

In G, 1 is the only node of lowest order (1), so we are forced to
pick it first. Then 2 is the only node adjacent to 1, so it must be
picked next. Then 4 is the only node adjacent to what was picked
before, so it must be picked next. Next, 6 is unique as the only
remaining node not adjacent to any already picked, so it must be
picked next. Finally there's a symmetry between 3 and 5, so we can
pick either arbitrarily.

In G', d is the only node of lowest order (1), so we are forced to
pick it first. [Hence 1 must map to d.] Then f is the only node
adjacent to d, so it must be picked next. [Hence 2 must map to f.]
But then there are two nodes (c,e) each adjacent to f, and two
nodes (a,b) neither adjacent to f, so the two graphs aren't
isomorphic, because there's nothing like 4 that it can map to.

Nothing as complicated as your algorithm is needed to decide this example.

Please try to find a pair of graphs whereby my simpleminded
algorithm isn't sufficient (to avoid backtracking) and your more
complicated algorithm works better (avoids backtracking entirely,
or reduces the amount of backtracking compared to my algorithm).
.

Relevant Pages

  • Re: New algorithm for the isomorphism of graphs
    ... [Hence 1 must map to d.] ... algorithm isn't sufficient (to avoid backtracking) and your more ... complicated algorithm works better (avoids backtracking entirely, ... The graphs posted were intended to show an example of how the ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... [Hence 1 must map to d.] ... algorithm isn't sufficient (to avoid backtracking) and your more ... complicated algorithm works better (avoids backtracking entirely, ... The two graphs are not isomorphism (except error of manual processing ...
    (sci.math)
  • Re: New algorithm for the isomorphism of graphs
    ... In G', d is the only node of lowest order, so we are forced to ... Nothing as complicated as your algorithm is needed to decide this example. ... Please try to find a pair of graphs whereby my simpleminded ... algorithm isn't sufficient (to avoid backtracking) and your more ...
    (sci.math)
  • Re: A dungeon generator
    ... rooms will not fit in the map, so your algorithm will fail. ... each level has 16 possible starting templates. ...
    (rec.games.roguelike.development)
  • Re: one sentence proof of 4 Color Mapping Problem; direct method
    ... for you to determine whether you can color this map with THREE ... So an algorithm for this machine would look ... building the algorithm in P to solve the NP-complete problems, ... Perhaps the equivalency is the idea that Eucl geom is what is ...
    (sci.math)