Re: New algorithm for the isomorphism of graphs

On 28 juil, 17:48, mimouni <mimouni.moha...@xxxxxxxxx> wrote:
On 28 juil, 06:12, Proginoskes <CCHeck...@xxxxxxxxx> wrote:

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- Masquer le texte des messages précédents -

- Afficher le texte des messages précédents -

The two graphs are not isomorphism (except error of manual processing
data).
Proves is in a Word file with 7 pages.
------
http://docs.google.com/Doc?id=dghj8t7n_26fgph9v



.

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
    ... 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: 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)
  • Re: A dungeon generator
    ... then it automatically turns in the former kind of algorithm. ... If it fails to generate a map ... rooms, then after a hundred more fails, five rooms, etc. ... each level has 16 possible starting templates. ...
    (rec.games.roguelike.development)