Re: New algorithm for the isomorphism of graphs

On Jul 27, 7:08 pm, i.am.a.w...@xxxxxxxxxxxxxxxx wrote:
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).

The graphs posted were intended to show an example of how the
algorithm worked, seeing as the OP's native language is not English.
If you want a challenge, try:

1 : 2 3 4 5
2 : 1 6 7 8
3 : 1 9 10 11
4 : 1 12 13 14
5 : 1 15 16 17
6 : 2 18 19 20
7 : 2 21 22 23
8 : 2 24 25 26
9 : 3 18 21 24
10 : 3 19 22 25
11 : 3 20 23 27
12 : 4 18 22 28
13 : 4 19 23 26
14 : 4 21 25 27
15 : 5 18 26 27
16 : 5 20 22 24
17 : 5 23 25 28
18 : 6 9 12 15
19 : 6 10 13 29
20 : 6 11 16 30
21 : 7 9 14 30
22 : 7 10 12 16
23 : 7 11 13 17
24 : 8 9 16 29
25 : 8 10 14 17
26 : 8 13 15 30
27 : 11 14 15 29
28 : 12 17 29 30
29 : 19 24 27 28
30 : 20 21 26 28

and

1 : 2 3 4 5
2 : 1 6 7 8
3 : 1 9 10 11
4 : 1 12 13 14
5 : 1 15 16 17
6 : 2 18 19 20
7 : 2 21 22 23
8 : 2 24 25 26
9 : 3 18 21 24
10 : 3 19 22 25
11 : 3 20 23 27
12 : 4 18 23 26
13 : 4 19 24 27
14 : 4 20 25 28
15 : 5 20 22 26
16 : 5 21 25 27
17 : 5 23 24 28
18 : 6 9 12 29
19 : 6 10 13 30
20 : 6 11 14 15
21 : 7 9 16 30
22 : 7 10 15 29
23 : 7 11 12 17
24 : 8 9 13 17
25 : 8 10 14 16
26 : 8 12 15 30
27 : 11 13 16 29
28 : 14 17 29 30
29 : 18 22 27 28
30 : 19 21 26 28

--- Christopher Heckman

.

Relevant Pages

  • Re: New algorithm for the isomorphism of graphs
    ... In G', d is the only node of lowest order, so we are forced to ... [Hence 1 must map to d.] ... Nothing as complicated as your algorithm is needed to decide this example. ... algorithm isn't sufficient (to avoid backtracking) and your more ...
    (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 graphs posted were intended to show an example of how the ...
    (sci.math)
  • Re: Sean PItman and nested hierarchy
    ... if God created life then the patterns in the ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ...
    (talk.origins)
  • Re: Sean PItman and nested hierarchy
    ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ... Separate creation can produce any pattern whatsoever, including a nested hierarchy. ...
    (talk.origins)
  • Re: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... graphs which are "pathological", so most of the time, you can solve NP- ... This is also why the average running time is not a good measure; ... isomorphism problem, where you only look at graphs with at most 400 ...
    (sci.math)