Ê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
Isomorphisme de graphes
Résumé
En mathématiques, dans le cadre de la théorie des graphes, un isomorphisme de graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes. Ce concept est en accord avec la notion générale d'isomorphisme, une bijection qui préserve les structures.
Plus précisément, un isomorphisme f entre les graphes G et H est une bijection entre les sommets de G et ceux de H, telle qu'une paire de sommets {u, v} de G est une arête de G si et seulement si {ƒ(u), ƒ(v)} est une arête de H.
L'isomorphisme peut aussi s'exprimer de la façon suivante : les graphes ont le même nombre de sommets et sont connectés de la même façon. Autrement dit, si les deux graphes venaient à être dessinés, alors il n'y aurait qu'à déplacer les sommets de l'un pour obtenir la copie conforme de l'autre (voir illustration).
On peut aussi définir un isomorphisme de graphes comme un morphisme de graphes bijectif et dont la bijection réciproque est aussi un morphisme de graphes.
Dans la définition ci-dessus, les graphes sont pris non orientés, non-étiquetés et non-pondérés. Cette notion se généralise aux graphes orientés (la bijection préserve alors aussi l'orientation) et aux graphes pondérés (la bijection préserve alors aussi la pondération).
Dans le cas de graphes étiquetés, on n'impose rien de plus à la bijection.
La notion d'isomorphisme de graphe permet de distinguer les propriétés inhérentes à leur structure des propriétés liées à leurs représentations. Par exemple, si le graphe possède exactement un cycle, alors tous les graphes qui lui sont isomorphes ont exactement un seul cycle. En revanche, le tracé du graphe, les structures de données associées, l'étiquetage, etc., ne seront pas identiques.
Si un isomorphisme existe entre deux graphes, les graphes sont dits isomorphes et on écrit . Dans le cas où la bijection est entre le graphe et lui-même, c'est-à-dire quand G et H sont un seul et même graphe, la bijection est appelée automorphisme du graphe G.
Les isomorphismes de graphe constituent une relation d'équivalence sur les graphes.
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.