Isomorphisme de graphes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Graphe G Graphe H Isomorphisme
entre G et H
Graph isomorphism a.svg Graph isomorphism b.svg ƒ(a) = 1

ƒ(b) = 6

ƒ(c) = 8

ƒ(d) = 3

ƒ(g) = 5

ƒ(h) = 2

ƒ(i) = 4

ƒ(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 (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.

Cas des graphes orientés, étiquetés et pondérés[modifier | modifier le code]

Dans la définition ci-dessus, les graphes sont pris non orientés, non-étiquetés et non-pondérés.

Néanmoins, cette notion peut aussi s'appliquer aux graphes orientés, si l'on demande à ce que la bijection préserve aussi l'orientation, et aux graphes pondérés, si l'on demande à ce que la bijection préserve aussi la pondération.

Dans le cas de graphes étiquetés, on n'impose rien de plus à la bijection.

Vocabulaire et propriétés[modifier | modifier le code]

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 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[modifier | modifier le code]

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 K3 et le graphe griffe K1,3 ne sont pas isomorphes, mais ont tous deux K3 comme graphe adjoint.

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

Aspects algorithmiques[modifier | modifier le code]

Le problème qui consiste, étant donné deux graphes à savoir si 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[modifier | modifier le code]

  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, no 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[modifier | modifier le code]

Source[modifier | modifier le code]

Articles connexes[modifier | modifier le code]