Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Automorphisme de graphe
Résumé
vignette|On peut définir deux automorphismes sur le graphe maison : l'identité et la permutation qui échange les deux « murs » de la « maison ».
En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes.
On peut voir l'automorphisme de graphes comme un isomorphisme de graphes du graphe dans lui-même. On peut en général s'arranger pour mettre en évidence visuellement les automorphismes de graphes sous forme de symétries dans le tracé du graphe.
Un automorphisme f d'un graphe G = (V, E) est une permutation dans l'ensemble des sommets V telle qu'une paire de sommets (u, v) forme une arête si et seulement si (f(u), f(v)) forme aussi une arête.
Les automorphismes peuvent être définis ainsi à la fois dans le cas des graphes orientés et des graphes non orientés.
Tout graphe possède au moins un automorphisme, l'identité, qui transforme chaque sommet en lui-même.
Si f est un automorphisme dans un graphe G et si u est un sommet de ce graphe, alors :
Autrement dit, un automorphisme de graphe ne modifie pas le degré des sommets d'un graphe. La réciproque n'est pas vraie : ce n'est pas parce qu'une permutation des sommets d'un graphe ne modifie pas leur degré que c'est un automorphisme.
La composition de deux automorphismes est un autre automorphisme. L'ensemble des automorphismes d'un même graphe muni de l'opération de composition forme un groupe, le groupe des automorphismes de ce graphe.
En sens inverse, le théorème de Frucht montre que tous les groupes peuvent être représentés par le groupe des automorphismes d'un graphe connexe, et même d'un graphe cubique.
vignette|Le graphe de Frucht a beau être 3-régulier, son seul automorphisme est l'identité.
Plusieurs familles de graphes sont définies d'après leurs automorphismes :
Un graphe asymétrique est un graphe dont le seul automorphisme est l'identité (illustration).
Un graphe sommet-transitif est un graphe dans lequel n'importe quel sommet peut être transformé en n'importe quel autre sommet par un automorphisme.
Source officielle
À 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.