Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Problème de l'isomorphisme de graphes
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.