Morphisme de graphes


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.

Sommaire

Définitions

Un homomorphisme entre deux graphes
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
Graph isomorphism a.svg Graph isomorphism b.svg ƒ(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 Kn. 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 v0 et que l'on va à v1 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 fV 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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Morphisme de graphes de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Morphisme — En mathématiques, un morphisme ou homomorphisme est une application entre deux ensembles munis d une même espèce de structure, qui respecte cette structure. Cette notion de morphismes est fondamentale en mathématique. Elle permet de comparer et… …   Wikipédia en Français

  • Homomorphisme de graphes — 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… …   Wikipédia en Français

  • Isomorphisme de graphes — 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… …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Théorie des graphes — Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une théorie informatique et mathématique. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette… …   Wikipédia en Français

  • Lexique De La Théorie Des Graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique de la theorie des graphes — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique en théorie des graphes — Lexique de la théorie des graphes Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A …   Wikipédia en Français

  • Lexique de la théorie des graphes — Article principal : Théorie des graphes. Sommaire : Haut A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Acyclique (grap …   Wikipédia en Français