Morphisme de graphes

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

Si ${\displaystyle G}$ et ${\displaystyle 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 ${\displaystyle f:V(G)\to V(H)}$ qui envoie les sommets de G sur ceux de H est un morphisme de graphes si : ${\displaystyle \forall (u,v)\in E(G)}$, ${\displaystyle (f(u),f(v))\in E(H)}$. Plus simplement, ${\displaystyle 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 à ${\displaystyle |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.

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

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 ${\displaystyle 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.

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 ${\displaystyle v_{0}}$ et que l'on va à ${\displaystyle v_{1}}$ par l'arête ${\displaystyle e_{v_{1}v_{2}}}$, alors on pourra faire le même chemin dans l'image par l'arête ${\displaystyle e_{f_{V}(v_{1}),f_{V}(v_{2})}}$ ; on obtient par induction que tout chemin de ${\displaystyle G}$ se retrouve par le chemin des images dans ${\displaystyle H}$.

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

Une extension au problème a été proposée en 2006[2] : en associant un sommet ${\displaystyle u\in V(G)}$ à un sommet ${\displaystyle i}$ de ${\displaystyle H}$, on paye un coût que l'on note ${\displaystyle 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 ${\displaystyle f_{V}}$ soit :

${\displaystyle \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 ${\displaystyle 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, c'est-à-dire aux applications suivantes : ${\displaystyle f:V(G)\rightarrow P(V(H))}$ telles que ${\displaystyle \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 ensembles partiellement ordonnés.

• Portail des mathématiques