Un algo poly pour l'isomorphisme de graphes

Je ne pense pas que mon algo soit le même que celui de la section 2.3 comme le dit Bisam. Il est polynomial en $N$ quelque soit le degré des sommets. Il est peut-être incomplet comme je l'ai dit et j'ai complété avec l'idée des bords....mais est-il encore polynomial ou déraille sur les bords ?

Je suis en train de voir une autre approche : trier la matrice d'adjacence des graphes pour obtenir une représentation minimale et donc canonique.

Certes, ce n'est pas simple puisque permuter deux lignes $i,j$ oblige aussi à permuter les deux mêmes colonnes.

Mais il semble se passer un miracle. Le tri par fusion semble possible. On coupe la matrice en deux parties. On trie chaque partie et on fusionne les deux parties triées. Les tests montrent que la matrice triée est toujours le résultat d'une telle fusion. C'est encore à prouver mais cela donnerait une méthode pour le test d'isomorphisme en $O(n^2log(n))$.

Cette forme normale obtenue par permutations indépendantes des lignes et colonnes est la plus petite possible dans l'ordre lexicographique.

Notons que ce n'est pas forcément la matrice d'un graphe. Il se peut que $M\not=M^t$ ou encore qu'il y ait un $1$ sur la diagonale.

Par exemple, pour le graphe

G={{1, 2}, {1, 4}, {2, 4}, {3, 5}}

on obtient à partir de sa matrice d'adjacence $$\left(\matrix{0&1&0&1&0\cr
1&0&0&1&0\cr 0&0&0&0&1\cr 1&1&0&0&0\cr 0&0&1&0&0\cr}\right)$$

et les permutations lignes/colonnes $[3, 5, 1, 2, 4]/[1, 2, 4, 3, 5]$, le réduit maximal :

$$\left(\matrix{0&0&0&0&1\cr 0&0&0&1&0\cr 0&1&1&0&0\cr 1&0&1&0&0\cr 1&1&0&0&0\cr}\right)$$

C'est un invariant comme un autre. Ce n'est plus forcément une matrice d'adjacence d'un graphe simple. C'est tout.

Ce qui est clair c'est que deux graphes isomorphes auront la même matrice minimale. Ce qui n'est pas clair c'est s'ils ne sont pas isomorphes alors les matrices minimales seront différentes. Je n'en sais rien.

Ce qui n'est pas clair non plus c'est si cet invariant peut être calculé vite. Pour la méthode brutale c'est en $O(N!^2)$....moche !

Bref vous aurez compris que je cherche à vous vendre un invariant pas forcément complet et qui se calcule laborieusement.