Morphisme de graphes

Un morphisme de graphe ou homomorphisme de graphe est une application entre deux graphes qui respecte la structure de ces graphes. Autrement dit l'image d'un graphe G dans un graphe H doit respecter les relations d'adjacence présentes dans G.

Définitions

Le graphe de gauche se projette dans le graphe de droite, par exemple de cette façon là

Si G et H sont deux graphes dont on note les sommets V(G) et V(H) et les arêtes E(G) et E(H), une application $f: V(G) \to V(H)$ qui envoie les sommets de G sur ceux de H est un morphisme de graphes si : $\forall (u,v) \in E(G)$, $(f(u),f(v)) \in E(H)$. Plus simplement, f est un morphisme de graphes si l'image de toute arête de G est une arête de H. S'il y a un morphisme de G dans H, on dit classiquement que G "se projette" dans H.

Cette définition est valable aussi bien pour les graphes orientés que non orientés. Elle s'étend pour les hypergraphes, orientés ou non.

S'il y un homomorphisme à la fois de G dans H et un de H dans G, on dit que G et H sont homomorphiquement équivalents (mais cela n'implique pas qu'ils soient isomorphes).

Il n'y a pas de règle générale régissant le nombre d'homomorphismes entre deux graphes quelconques, qui peut aller de 0 à | V(H) | ^{| V(G) |} .

Les graphes associés aux homomorphismes de graphes forment une catégorie au sens de la théorie des catégories.

Un cas particulier : l'isomorphisme de graphes

On dit de l'homomorphisme f qu'il est une injection (respectivement surjection) si f est injective (respectivement surjective) ; si elle est à la fois injective et surjective, c'est-à-dire bijective, et que sa réciproque est également un homomorphisme, alors on dit que f est un isomorphisme.

L'isomorphisme peut aussi s'exprimer de la façon suivante : les graphes ont le même nombre de sommets, c'est-à-dire V(G) = V(H), 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, comme cela est illustré ci-dessous.

Cette notion nous permet d'introduire celle de l'étiquetage : à chaque sommet est associé une étiquette, souvent un entier allant de 1 à V(G) = n mais il peut s'agir d'un alphabet quelconque permettant ainsi à l'étiquette d'un sommet de contenir des renseignements sur sa localisation (qui pourront ensuite être utilisés pour des problèmes de routage). Si on s'intéresse aux graphes étiquetés, alors il suffit que les étiquettes de certains sommets soient différentes pour que l'on considère les graphes différents ; cependant, les graphes peuvent être équivalents au niveau de la structure et on dira qu'ils sont isomorphes.

Graphe G	Graphe H	Isomorphisme entre G et H
		ƒ(a) = 1 ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7

Un deuxième cas particulier : l'automorphisme de graphe

Un isomorphisme d'un graphe sur lui-même est appelé un automorphisme.

Il est parfois intéressant d'étudier les homomorphismes d'un graphe dans lui même. On définit ainsi la notion de graphe core. Un graphe est dit core lorsque tout homomorphisme de ce graphe sur lui-même est un isomorphisme. Tout graphe est homomorphiquement équivalent a un unique graphe core (défini à l'isomorphisme près).

Notation et cardinalités

La notation^[1] HOM(G,H) dénote l'ensemble des homomorphismes $f: G \to H$ et hom(G,H) est le nombre de tels homomorphismes, c'est-à-dire la cardinalité de HOM(G,H). On utilise les notations INJ(G,H) pour l'injection, SUR(G,H) pour la surjection et BIJ(G,H) pour la bijection.

Problème de la H-coloration

Un problème très classique en théorie des graphes est de déterminer si un graphe G est colorable avec un nombre déterminé n de couleurs. Ce problème revient à se demander si le graphe G se projette dans le graphe complet K_n. C'est pourquoi le problème de savoir si un graphe G se projette dans un graphe H est parfois appelé problème de la "H-coloration". Ce problème est aussi parfois appelé problème H-CSP, lorsque H peut être un hypergraphe. H est alors vu comme le graphe de contraintes associé à un problème CSP.

Problème du chemin

Une propriété de l'homomorphisme découlant directement de la définition concerne l'existence d'un chemin : la contrainte sur la structure impose à toute arête du graphe d'origine d'exister dans l'image.

Si l'on se trouve sur le sommet v₀ et que l'on va à v₁ par l'arête $e_{v_1v_2}$, alors on pourra faire le même chemin dans l'image par l'arête $e_{f_V(v_1),f_V(v_2)}$ ; on obtient par induction que tout chemin de G se retrouve par le chemin des images dans H.

Ceci implique par exemple que si G se projette dans H, la maille de G est supérieure à celle de H.

Extensions et variantes

Une extension au problème a été proposée en 2006^[2] : en associant un sommet $u \in V(G)$ à un sommet i de H, on paye un coût que l'on note $c_i(u), i \in V(H)$, et l'on peut alors définir le coût d'un homomorphisme par l'ensemble du coût donné par chaque association de f_V soit :

$\sum_{u \in V(G)}c_{f_V(u)}(u)$

Le but est de déterminer s'il existe un homomorphisme dont le coût ne dépasse pas une limite k.

Parmi les autres variantes du problème, on peut spécifier pour chaque sommet une liste d'images permises^[3]. Cette variante généralise le problème de la coloration par liste.

Une autre extension du problème consiste à s'intéresser aux multi-homomorphismes entre deux graphes, i.e aux applications suivantes : $f:V(G)\rightarrow P(V(H))$ telles que $\forall(x,y)\in E(G), \forall(u,v)\in f(x)\times f(y), (u,v)\in E(H)$ L'ensemble des multi-homomorphismes entre deux graphes peut être vu comme un élément de la catégorie des posets.

Notes et références

1. ↑ (en) Pavol Hell et Jaroslav Nesetril, Graphs and Homomorphisms, Oxford University Press, 2004. (ISBN 0198528175)
2. ↑ (en) Gregory Gutin, Arash Rafiey et A. Yeo, « Level of repair analysis and minimum cost homomorphisms of graphs », in Discrete Applied Math., volume 154, p. 890-897, 2006.
3. ↑ (en) Pavol Hell, « Algorithmic aspects of graph homomorphisms », in Survey in Combinatorics, London Math. Society, Cambridge University Press, pages 239-276, 2003.