Algorithme polynomial pour les graphes isomorphes

[medmimo]

Bonjour,
j'ai trouver un algorithme polynomial de complexité qui teste l'isomorphisme entre deux graphes simple, et je veux savoir si la démonstration mathématique est vrai ou non.
Et voici le document:isomorphespolynomial.pdf.

Et merci a vous.
-----

[Resartus]

Bonjour,
Il me semble que votre démonstration présuppose qu'il existe un isomorphisme.
C'est un résultat déjà connu que dans ce cas, l'algorithme pour le construire est en effet en O(n^3).

Ce qui est plus difficile est de tester si deux graphes sont isomorphes : la complexité des meilleurs algorithmes de test est alors exponentielle.

[medmimo]

Merci monsieur

Exactement es que les autres types (multigraphes, hypergraphes, graphes avec boucle) sont plus difficiles par rapport à un graphe simple ?
C’est quoi un cas difficile pour ce problème ?