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 modifier
| Graphe G | Graphe H | Isomorphisme entre G et H |
|---|---|---|
|
|
|
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 modifier
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 modifier
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. 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
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
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 modifier
- (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, , p. 150-168 (lire en ligne)
- (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
Source modifier
- (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).
