vignette|Le problème est de savoir si deux graphes sont les mêmes. En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. Ce problème est particulièrement important en théorie de la complexité, plus particulièrement pour le problème P=NP. En effet, le problème de l'isomorphisme de graphes est l'un des problèmes de NP, pour lequel on ne connaît ni d'algorithme en temps polynomial ni de preuve de NP-complétude. On le soupçonne être un problème NP-intermédiaire. Cependant le problème peut être résolu en temps polynomial pour certaines classes de graphes, par exemple les graphes planaires ou les graphes de degré borné et en temps quasi-polynomial pour le cas général. Ce problème peut-être vu comme une restriction du problème de l'isomorphisme de sous-graphes. où les graphes G et H ont le même nombre de sommets. En pratique, l'isomorphisme de graphes est utilisé en chimie pour classer les molécules. Un isomorphisme d'un graphe G vers un graphe H est une bijection de l'ensemble des sommets de G dans l'ensemble des sommets de H, qui respecte les arêtes, c'est-à-dire : est une arête dans G si et seulement si est une arête dans H. Le problème de l'isomorphisme de graphes est le problème de décision suivant : Entrée : G et H, deux graphes Question : G et H sont-ils isomorphes ? Dans le cas général, plusieurs approches algorithmiques existent. Les trois plus classiques sont : L'utilisation d'invariants de sommets, qui sont des entiers associés aux sommets tels que deux sommets équivalents de deux graphes isomorphes ont la même valeur. On peut citer par exemple le degré, la distance à un sommet particulier, la taille de la clique maximum contenant le sommet etc. Si les deux graphes n'ont pas les mêmes invariants ils sont différents. On peut raffiner ce genre d'argument, mais il reste toujours la difficulté du choix des invariants et cela ne réduit pas toujours l'espace de recherche.