Isomorphisme de graphes

Bonjour

J'ai vu que l'isomorphisme entre deux graphes quelconques G1 G2 revient à chercher un isomorphisme entre deux graphes bipartis G1' et G2'.



Or un graphe biparti, on peut le munir d'un ordre ; donc chercher un isomorphisme entre deux graphes quelconques revient à chercher un isomorphisme (voir un automorphisme ) entre deux graphes ordonnés.

Ma questions est la suivante :

- Décider de l’existence d’un isomorphisme ou automorphisme entre deux graphes G1 et G2 ordonnés est dans NP ? qu'en est-il de leur temps de calcul (complexité) ?
- De première vue comparer deux diagrammes de Hasse ne doit pas prendre un temps de calcul exponentiel !!

Merci

[Helmut Hasse 1898-1979 te remercie pour sa majuscule.]