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

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (5)
PHYS-512: Statistical physics of computation
The students understand tools from the statistical physics of disordered systems, and apply them to study computational and statistical problems in graph theory, discrete optimisation, inference and m
COM-406: Foundations of Data Science
We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an
CS-250: Algorithms I
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
Afficher plus
Publications associées (74)
Concepts associés (13)
Produit tensoriel (graphe)
Le produit tensoriel est une opération sur deux graphes et résultant en un graphe . Il est également appelé produit direct, produit de Kronecker ou produit catégorique. Soient deux graphes et . Le produit tensoriel est défini comme suit : l'ensemble de ses sommets est le produit cartésien ; et sont adjacents dans si et seulement si et sont adjacents dans et et sont adjacents dans . Autrement dit, deux sommets sont voisins si les sommets dont ils sont issus étaient voisins dans les deux graphes.
Complexity of constraint satisfaction
The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction problems on finite domains. Solving a constraint satisfaction problem on a finite domain is an NP-complete problem in general. Research has shown a number of polynomial-time subcases, mostly obtained by restricting either the allowed domains or constraints or the way constraints can be placed over the variables.
Graphe de Mycielski
En théorie des graphes, les graphes de Mycielski, ou myscielkiens, sont des graphes sans triangles de nombre chromatique élevé, construits par récurrence à partir du graphe formé d'un unique sommet par une transformation appelée elle aussi myscielskien. Ils sont dus au mathématicien Jan Mycielski. Soit un graphe. Le mycielkien de ce graphe noté est le graphe avec où est une copie de et où et . Les graphes de Mycielski sont les graphes définis par la récurrence suivante : est le graphe à une arête, et .
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.