problème de l'isomorphisme de graphes

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[réf. souhaitée]. 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.