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.

Définitions

Graphe G	Graphe H	Isomorphisme entre G et H
		${\displaystyle f(a)=1}$ ${\displaystyle f(b)=6}$ ${\displaystyle f(c)=8}$ ${\displaystyle f(d)=3}$ ${\displaystyle f(g)=5}$ ${\displaystyle f(h)=2}$ ${\displaystyle f(i)=4}$ ${\displaystyle f(j)=7}$

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.

Généralisation aux graphes orientés, étiquetés et pondérés

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.

Vocabulaire et propriétés

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 ${\displaystyle G\simeq H}$. 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. En tant que tels, ils partagent les graphes en classes d'équivalence. L'ensemble des graphes isomorphes entre eux est une classe d'isomorphisme de graphes.

Théorème de Whitney

L'exception du théorème de Whitney : ces deux graphes ne sont pas isomorphes entre eux, mais ont des graphes adjoints isomorphes.

Le théorème de Whitney sur les isomorphismes de graphes^[1], démontré par Hassler Whitney, affirme que deux graphes connexes sont isomorphes si et seulement si leurs graphes adjoints sont isomorphes, avec une seule exception : le graphe triangle K₃ et le graphe griffe K_1,3 ne sont pas isomorphes, mais ont tous deux K₃ comme graphe adjoint.

Le théorème de Whitney sur les graphes peut être étendu aux hypergraphes^[2].

Aspects algorithmiques

Le problème qui consiste, étant donné deux graphes à savoir s'ils sont isomorphes, est un problème algorithmique classique. Il est notamment connu en théorie de la complexité pour être l'un des seuls problèmes de la classe NP pour lequel on ne connait ni d'algorithme en temps polynomial, ni de preuve qu'il est NP-complet. Il existe cependant des algorithmes en temps polynomial pour de nombreuses classes de graphes, comme ceux de degrés bornés.

Notes et références

1. (en) Hassler Whitney, « Congruent Graphs and the Connectivity of Graphs », American Journal of Mathematics (Am. J. Math.), The Johns Hopkins University Press, vol. 54, n^o 1,‎ janvier 1932, p. 150-168 (lire en ligne)
2. (en) Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.

Voir aussi

Source

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Graph isomorphism » (voir la liste des auteurs).

Articles connexes

• Morphisme de graphes
• Problème de l'isomorphisme de graphes