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 dans un graphe doit respecter les relations d'adjacence présentes dans . thumb|alt=Un homomorphisme entre deux graphes|Le graphe de gauche se projette dans le graphe de droite, par exemple de cette façon là Si et sont deux graphes dont on note les sommets V(G) et V(H) et les arêtes E(G) et E(H), une application qui envoie les sommets de G sur ceux de H est un morphisme de graphes si : , . Plus simplement, 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 à . Les graphes associés aux homomorphismes de graphes forment une catégorie au sens de la théorie des catégories. On dit de l'homomorphisme qu'il est une injection (respectivement surjection) si 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. 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).