Instances matérielles pour les tests d'isomorphisme de graphe

Le cas des graphiques fortement réguliers est-il le plus difficile à tester GI?

où "le plus dur" est utilisé dans un sens "commun", ou "en moyenne", pour ainsi dire.
Wolfram MathWorld mentionne quelques "graphiques pathologiquement durs". Que sont-ils?

Mon échantillon de 25 paires de graphiques: http://funkybee.narod.ru/graphs.htm J'ai testé beaucoup d'autres mais tous du même type - SRG ou RG de http://www.maths.gla.ac .uk / ~ es / srgraphs.html ou de genreg.exe. Si je génère, disons, 1000 graphiques, je teste toutes les 1000 * (1000 - 1) / 2 paires. Bien sûr, je ne teste pas de cas évidents ("idiots"), par exemple, des graphiques avec différents vecteurs triés de degrés, etc. Mais le processus semble sans fin et, dans une certaine mesure, sent vain. Quelle stratégie de test dois-je choisir? Ou cette question est-elle presque égale au problème de l'IG lui-même?

J'ai même redessiné sur papier un graphique de thesis_pascal_schweitzer.pdf
(suggéré par @ 5501). Sa belle photo: http://funkybee.narod.ru/misc/furer.jpg
Je ne suis pas sûr mais semble exactement ce genre de graphiques "que l'algorithme de
Weisfeiler-Lehman k-dimensionnel ne peut pas distinguer."
Mais, messieurs, copier des graphiques sur papier à partir de livres électroniques, c'est trop pour moi.

25

0100000000000000000000000
1010000000000000000000000
0101000000000000000000100
0010100000000010000000000
0001010000001000000000000
0000101000000000000000000
0000010100000000000000000
0000001010000000000000000
0000000101000000000000000
0000000010100000000000000
0000000001010000000000000
0000000000101000000000100
0000100000010000000000010
0000000000000010000001010
0001000000000101000000000
0000000000000010100000000
0000000000000001010000000
0000000000000000101000000
0000000000000000010100000
0000000000000000001010000
0000000000000000000101000
0000000000000100000010100
0010000000010000000001000
0000000000001100000000001
0000000000000000000000010

0100000000000000000000000
1010000000000000000000000
0101000000000000000000100
0010100000000010000000000
0001000000001000000010000
0000001000000000000001000
0000010100000000000000000
0000001010000000000000000
0000000101000000000000000
0000000010100000000000000
0000000001010000000000000
0000000000101000000000100
0000100000010000000000010
0000000000000010000001010
0001000000000101000000000
0000000000000010100000000
0000000000000001010000000
0000000000000000101000000
0000000000000000010100000
0000000000000000001010000
0000100000000000000100000
0000010000000100000000100
0010000000010000000001000
0000000000001100000000001
0000000000000000000000010

Bounty demandant:
===========
Quelqu'un pourrait-il confirmer que les 2 dernières paires (# 34 et # 35 dans la zone de texte de gauche: http://funkybee.narod.ru/graphs.htm ) sont isomorphes?
Le problème est qu'ils sont basés sur ceci: http://funkybee.narod.ru/misc/mfgraph2.jpg de A Counterexample in Graph Isomorphism Testing (1987) de M. Furer mais je n'ai pas pu les obtenir NON isomorphes. .

PS # 1
J'ai pris 4 (doit être même carré d'un certain nombre positif (m ^ 2)) pièces fondamentales, les a alignées en queue d'aronde, - j'ai donc obtenu le 1er graphique global, dans sa copie, j'ai échangé (entrecroisé) 2 centrales bords dans chacun des 4 morceaux - j'ai donc obtenu le 2ème graphique global. Mais ils sont devenus isomorphes. Qu'est-ce que j'ai raté ou mal compris dans le conte de Furer?

PS # 2 On
dirait que je l'ai.
3 paires # 33, # 34 et # 35 (les 3 dernières paires sur http://funkybee.narod.ru/graphs.htm ) sont des cas vraiment incroyables.

Paire # 34:
        G1 et G2 sont des graphes non isomorphes.
        En G1: bords (1-3), (2-4). En G2: bords (1-4), (2-3).
        Plus de différences en eux.

Paire # 35:
        G11 et G22 sont des graphes isomorphes.
        G11 = G1 et G22 est une copie de G2, avec une seule différence:
        Les bords (21-23), (22-24) ont été échangés comme ceci: (21-24), (22-23)
        ... et deux graphiques deviennent isomorphes
        comme si 2 swaps s'anéantissaient.
        Un nombre impair de ces échanges rend les graphiques à nouveau NON isomorphes

Le graphique # 33 (20 sommets, 26 arêtes) est toujours le suivant: http://funkybee.narod.ru/misc/mfgraph2.jpg Les
graphiques de ## 34, 35 ont été créés simplement en couplant 2 graphiques de base (# 33) - chacun obtenant 40 sommets et 60 = 26 + 26 + 8 arêtes. Par 8 nouveaux bords, je connecte 2 "moitiés" de ce nouveau ("gros") graphique. Vraiment incroyable et exactement comme Martin Furer le dit ...

Cas n ° 33: g = h ("h" est "g avec un changement de bord possible en son milieu"
                                                  (regarder la photo))

Cas n ° 34: g + g! = G + h (!!!)


Cas n ° 35: g + g = h + h (!!!)

$GI \not\in P$$P \neq NP$

Tout lien vers d'autres résultats serait très apprécié.

Pour la paire 35 j'ai trouvé:
1: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
2: 6,7,9,10, 15,16,18,19,26,27,29,30,35,36,38,39
3: 1,2,3,4,21,22,23,24
4: 5,8,11,12, 13,14,17,20,25,28,31,32,33,34,37,40
5: 5,8,11,12,13,14,17,20,25,28,31,32,33 , 34,37,40
6: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
7: 5,8,11,12,13 , 14,17,20,25,28,31,32,33,34,37,40
8: 6,7,9,10,15,16,18,19,26,27,29,30,35, 36,38,39
9: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
10: 6,7,9,10,15, 16,18,19,26,27,29,30,35,36,38,39
11: 1,2,3,4,21,22,23,24
12: 5,8,11,12,13, 14,17,20,25,28,31,32,33,34,37,40
13: 5,8,11,12,13,14,17,20,25,28,31,32,33,34 , 37,40
14: 1,2,3,4,21,22,23,24
15: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
16: 6,7,9,10,15,16,18,19 , 26,27,29,30,35,36,38,39
17: 1,2,3,4,21,22,23,24
18: 5,8,11,12,13,14,17,20 , 25,28,31,32,33,34,37,40
19: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
20 : 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
21: 5,8,11,12,13,14,17,20, 25,28,31,32,33,34,37,40
22: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
23: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
24: 6,7,9,10,15,16,18,19,26 , 27,29,30,35,36,38,39
25: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
26: 1 , 2,3,4,21,22,23,24
27: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
28: 5 , 8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
29: 1,2,3,4,21,22,23,24
30: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
31: 6,7,9,10,15,16,18,19 , 26,27,29,30,35,36,38,39
32: 1,2,3,4,21,22,23,24
33: 6,7,9,10,15,16,18,19 , 26,27,29,30,35,36,38,39
34: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
35 : 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
36: 6,7,9,10,15,16,18,19, 26,27,29,30,35,36,38,39
37: 5,8,11,12,13,14,17,20,25,28,31,32,33,34,37,40
38: 1,2,3,4,21,22,23,24
39: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39
40: 6,7,9,10,15,16,18,19,26,27,29,30,35,36,38,39

Je n'ai pas encore fini d'écrire le script pour vérifier les résultats.