Morphisme de graphes

Un morphisme de graphes ou homomorphisme de graphes est une application entre deux graphes (orientés ou non orientés) qui respecte la structure de ces graphes. Autrement dit l'image d'un graphe ${\displaystyle G}$ dans un graphe ${\displaystyle H}$ doit respecter les relations d'adjacence présentes dans ${\displaystyle G}$.

Définitions

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.

Cas particuliers

Injections et surjections

On dit de l'homomorphisme ${\displaystyle f}$ qu'il est une injection (respectivement surjection) si ${\displaystyle f}$ est injective (respectivement surjective).

Isomorphisme de graphes

Si un homomorphisme est à la fois injectif et surjectif, c'est-à-dire bijectif, et que sa réciproque est également un homomorphisme, alors on dit que f est un isomorphisme.

Automorphisme de graphe

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

Endomorphisme de graphes

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 à un unique graphe core (défini à l'isomorphisme près)^{[réf. nécessaire]}.

Notation et cardinalités

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.

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

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

Extensions et variantes

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.

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.