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 $G$ dans un graphe $H$ doit respecter les relations d'adjacence présentes dans $G$ .

Définitions[modifier | modifier le code]

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.

Cas particuliers[modifier | modifier le code]

Injections et surjections[modifier | modifier le code]

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

Isomorphisme de graphes[modifier | modifier le code]

Article détaillé : 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[modifier | modifier le code]

Article détaillé : Automorphisme de graphe.

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

Endomorphisme de graphes[modifier | modifier le code]

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

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

Problème de la H-coloration[modifier | modifier le code]

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

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_{0}$ et que l'on va à $v_{1}$ par l'arête $e_{v_{1}v_{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[modifier | modifier le code]

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, c'est-à-dire 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 ensembles partiellement ordonnés.

Notes et références[modifier | modifier le code]

↑ (en) Pavol Hell et Jaroslav Nesetril, Graphs and Homomorphisms, Oxford University Press, 2004. (ISBN 0198528175)
↑ (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.
↑ (en) Pavol Hell, « Algorithmic aspects of graph homomorphisms », in Survey in Combinatorics, London Math. Society, Cambridge University Press, pages 239-276, 2003.

Portail des mathématiques

[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.

[1]

[2]

[3]