Isomorphisme de graphes

En algèbre, on dit de deux structures qu'elles sont isomorphes lorsqu'il existe une correspondance entre leurs éléments qui préserve leur structure. En particulier, on observe que les propriétés structurelles de deux graphes $G$ et $H$ sont les mêmes s'il est possible de renommer les sommets de $G$ avec les noms des sommets de $H$ de sorte à ce que $G$ devienne $H$.

Un isomorphisme entre deux graphes simples $G = (V_G, E_G)$ et $H = (V_H, E_H)$ est une bijection $f: V_G \longrightarrow V_H$ telle que $(f(u), f(v)) \in E_H$ si et seulement si $(u, v) \in E_G$. Si un tel isomorphisme existe, on dit que $G$ est isomorphe à $H$, et l'on écrit $G \cong H$.

La relation "être isomorphe à" est une relation d'équivalence sur l'ensemble des graphes simples. Une classe d'équivalence selon cette relation est appelée classe d'isomorphisme de graphes et peut être identifiée à un graphe non étiqueté.

Dans le cas où $G = H$, on a la définition suivante : un automorphisme $f$ d'un graphe $G = (V, E)$ est une permutation de $V$ telle que $(f(u), f(v)) \in E$ si et seulement si $(u, v) \in E$.

L'ensemble des automorphismes d'un graphe $G$ est non vide car il contient l'application identité. Il est par ailleurs stable par l'opération de composition et par passage à l'inverse : c'est donc un groupe.

Les propriétés structurelles d'un graphe (ordre, connexité, etc.) sont préservées par isomorphisme.