Quelqu'un connaît-il un contre-exemple de l'algorithme d'isomorphisme du graphique Dharwadker-Tevet?

À http://www.dharwadker.org/tevet/isomorphism/ , il y a une présentation d'un algorithme pour déterminer si deux graphiques sont isomorphes. Étant donné un certain nombre de déclarations «intéressantes» de A Dharwadker, je ne suis pas enclin à y croire.

Dans mon enquête, je trouve que l'algorithme produira certainement la bonne réponse et vous dira que deux graphiques ne sont pas isomorphes alors qu'en fait c'est correct. Cependant, il n'est pas clair que l'algorithme vous dira systématiquement si deux graphiques sont isomorphes alors qu'ils le sont réellement. La "preuve" de leur résultat laisse à désirer.

Cependant, je ne connais pas de contre-exemple. Avant de commencer à écrire un logiciel pour tester l'algorithme, j'ai pensé que je verrais si quelqu'un était déjà au courant d'un contre-exemple.

Quelqu'un a demandé un résumé de l'algorithme. Je ferai ce que je peux ici, mais pour vraiment le comprendre, vous devriez visiter http://www.dharwadker.org/tevet/isomorphism/ .

L'algorithme comporte deux phases: une phase de "signature" et une phase de tri. La première phase de "signature" (c'est mon terme pour leur processus; ils l'appellent générer la "matrice de signe") trie efficacement les sommets en différentes classes d'équivalence. La deuxième phase ordonne d'abord les sommets en fonction de leur classe d'équivalence, puis applique une procédure de tri au sein des classes d'équivalence pour établir un isomorphisme entre les deux graphiques. Fait intéressant, ils ne prétendent pas établir une forme canonique pour les graphiques - au lieu de cela, un graphique est utilisé comme une sorte de modèle pour le second.

La phase de signature est en fait assez intéressante, et je ne rendrais pas justice ici en essayant de la paraphraser. Si vous souhaitez plus de détails, je vous recommande de suivre le lien pour examiner sa phase de signature. La "matrice de signe" générée conserve certainement toutes les informations sur le graphique d'origine et établit ensuite un peu plus d'informations. Après avoir collecté les signatures, ils ignorent la matrice d'origine car les signatures contiennent toutes les informations sur la matrice d'origine. Il suffit de dire que la signature effectue une opération qui s'applique à chaque arête liée au sommet, puis ils collectent le multi-ensemble d'éléments pour un sommet pour établir une classe d'équivalence pour le sommet.

La deuxième phase - la phase de tri - est la partie douteuse. En particulier, je m'attendrais à ce que si leur processus fonctionnait, alors l'algorithme développé par Anna Lubiw pour fournir un "Ordre doublement lexical des matrices" (Voir: http://dl.acm.org/citation.cfm?id=22189 ) fonctionnerait également pour définir une forme canonique pour un graphique.

Pour être juste, je ne comprends pas entièrement leur processus de tri, même si je pense qu'ils font un travail raisonnable pour le décrire. (Je n'ai tout simplement pas travaillé sur tous les détails). En d'autres termes, il me manque peut-être quelque chose. Cependant, on ne sait pas comment ce processus peut faire bien plus que de trouver accidentellement un isomorphisme. Bien sûr, ils le trouveront probablement avec une forte probabilité, mais pas avec une garantie. Si les deux graphiques ne sont pas isomorphes, le processus de tri ne le trouvera jamais et le processus rejette correctement les graphiques.

Pour graphA.txt:

25
 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0
 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0
 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1
 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1
 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0
 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1
 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0
 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0
 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1
 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1
 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0
 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1
 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1
 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0
 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0
 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0
 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1
 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1
 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1
 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0

et graphB.txt:

25
 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0
 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0
 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0
 1 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0
 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1
 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0
 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1
 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1
 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1
 1 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0
 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1
 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1
 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0
 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0
 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1
 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0
 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0
 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 0
 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1
 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1
 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1
 0 0 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 1
 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0
 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0

qui est obtenu à partir graphA.txtde l'application de la permutation (aléatoire)

 22 9 24 11 15 8 5 18 13 14 2 10 23 0 3 17 4 16 6 19 7 21 12 1 20

le programme C ++ isororphism.cppde la figure 6.3. Un programme C ++ pour l'algorithme d'isomorphisme graphique dans http://www.dharwadker.org/tevet/isomorphism/ fournit les résultats suivants:

The Graph Isomorphism Algorithm
by Ashay Dharwadker and John-Tagore Tevet
http://www.dharwadker.org/tevet/isomorphism/
Copyright (c) 2009
Computing the Sign Matrix of Graph A...
Computing the Sign Matrix of Graph B...
Graph A and Graph B have the same sign frequency vectors in lexicographic order but cannot be isomorphic.
See result.txt for details.

Nous pouvons donc supposer qu'il s'agit d'un contre-exemple de l'algorithme d'isomorphisme du graphique Dharwadker-Tevet.

Comme suggéré par Bill Province, le problème est

$G_A$$G_B$

L'objection de Bill Province est que la preuve de la proposition 4.1. n'utilise aucune propriété spéciale de la matrice de signe qui ne s'appliquerait pas également à la matrice d'adjacence. Plus précisément, l'étape suivante de la preuve est erronée:

$1, ..., t$$A$$B$$1, ..., t$$A$$v_1, ..., v_t$$1, ..., t$$B$$φ(v_1) = v'_1, ..., φ(v_t) = v'_t$

$φ$

Parce qu'un trou dans la preuve d'exactitude a été identifié, le contre-exemple ci-dessus devrait être suffisant pour réfuter l'exactitude prétendue de l'algorithme proposé.

Remerciements Le contre-exemple est la première des huitièmes paires de graphiques de

http://funkybee.narod.ru/graphs.htm

Pour manipuler les graphiques, j'ai utilisé et modifié le code source de ScrewBoxR1160.tar trouvé sur

https://people.mpi-inf.mpg.de/~pascal/software/

Pour comprendre le trou dans la preuve d'exactitude, le commentaire d'András Salamon sur Weisfeiler-Lehman a été très utile, tout comme les explications de

http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

La motivation pour utiliser cette question comme une opportunité de se familiariser avec nauty / Traces et les aspects pratiques de l'isomorphisme graphique a été fournie par vzn. L'avantage d'apprendre à utiliser des programmes de pointe pour les isomorphismes de graphes a valu la peine de consacrer un peu de temps à trouver un contre-exemple (que je croyais fermement exister).