Isomorphisme de graphes

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.