Automorphisme de graphe

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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.

Définition formelle[modifier | modifier le code]

Un automorphisme f d'un graphe G = (VE) est une permutation dans l'ensemble des sommets V telle qu'une paire de sommets (uv) 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.

Propriétés[modifier | modifier le code]

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 :

deg(f(u)) = deg(u)

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

Composition d'automorphismes[modifier | modifier le code]

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 (en) montre que tous les groupes peuvent être représentés par le groupe des automorphismes d'un graphe connexe[2], et même d'un graphe cubique[3].

Les familles de graphes définies par leurs automorphismes[modifier | modifier le code]

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 (en) est un graphe dans lequel n'importe quel sommet peut être transformé en n'importe quel autre sommet par un automorphisme.
  • Un graphe arête-transitif (en) est un graphe dans lequel n'importe quelle arête peut être transformée en n'importe quelle autre arête par un automorphisme.
  • Un graphe symétrique est un graphe dans lequel n'importe quelle paire de sommets adjacents peut être transformée par un automorphisme en une autre paire de sommets adjacents.
  • Un graphe graphe distance-transitif (en) est un graphe dans lequel n'importe quelle paire de sommets peut être transformée en n'importe quelle autre paire de sommets à la même distance l'un de l'autre par un automorphisme.
  • Un graphe semi-symétrique (en) est un graphe qui est arête-transitif mais pas sommet-transitif.
  • Un graphe demi-symétrique (en) est un graphe qui est arête-transitif et sommet-transitif, mais pas symétrique.

Les relations d'inclusion entre ces familles sont indiquées par le schéma suivant :

Dodécaèdre
Arrow east.svg
Graphe de Shrikhande
Arrow west.svg
Graphe de Paley
Graphe distance-transitif (en) Graphe distance-régulier Graphe fortement régulier
Arrow south.svg
Graphe F26A
Arrow west.svg
Graphe de Nauru
Graphe symétrique (arc-transitif) Graphe t-transitif, t ≥ 2
Arrow south.svg
(si connexe)
Graphe de Holt
Arrow east.svg
Graphe de Folkman
Arrow east.svg
Graphe biparti complet K3,5
Graphe demi-transitif (en) Graphe semi-symétrique (en) Graphe arête-transitif (en)
Arrow south.svg
Arrow south.svg
Tétraèdre tronqué
Arrow east.svg
Graphe de Frucht
Graphe sommet-transitif (en) Graphe régulier
Arrow north.svg
Prisme triangulaire
Graphe de Cayley

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

  1. Charles Delorme et M.-C. Heydemann, Graphes de Cayley - Définitions, site du Laboratoire de Recherche en Informatique de l'Université Paris-Sud.
  2. (de) R. Frucht, « Herstellung von Graphen mit vorgegebener abstrakter Gruppe », Compositio Mathematica, vol. 6,‎ 1938, p. 239–250 (ISSN 0010-437X, lien zbMATH?, lire en ligne).
  3. (en) R. Frucht, « Graphs of degree three with a given abstract group », Canadian Journal of Mathematics, vol. 1, no 4,‎ 1949, p. 365–378 (ISSN 0008-414X, lien DOI?, lire en ligne).

Voir aussi[modifier | modifier le code]

Source[modifier | modifier le code]

Articles connexes[modifier | modifier le code]