Automorphisme des graphes - Graph automorphism
Dans le domaine mathématique de la théorie des graphes , un automorphisme d'un graphe est une forme de symétrie dans laquelle le graphe est mappé sur lui-même tout en préservant la connectivité arête-sommet.
Formellement, un automorphisme d'un graphe G = ( V , E ) est une permutation σ de l'ensemble de sommets V , telle que la paire de sommets ( u , v ) forme une arête si et seulement si la paire (σ( u ), σ( v )) forment également une arête. C'est-à-dire qu'il s'agit d'un isomorphisme de graphe de G à lui-même. Les automorphismes peuvent être définis de cette manière aussi bien pour les graphes orientés que pour les graphes non orientés . La composition de deux automorphismes est un autre automorphisme, et l'ensemble des automorphismes d'un graphe donné, sous l'opération de composition, forme un groupe , le groupe d'automorphismes du graphe. Dans la direction opposée, par le théorème de Frucht , tous les groupes peuvent être représentés comme le groupe d'automorphisme d'un graphe connexe – en fait, d'un graphe cubique .
Complexité de calcul
Construire le groupe d'automorphisme est au moins aussi difficile (en termes de complexité de calcul ) que de résoudre le problème d'isomorphisme de graphe , en déterminant si deux graphes donnés correspondent sommet pour sommet et bord pour bord. Car, G et H sont isomorphes si et seulement si le graphe déconnecté formé par l' union disjointe des graphes G et H a un automorphisme qui permute les deux composantes. En fait, le simple comptage des automorphismes est équivalent en temps polynomial à l'isomorphisme de graphe.
Le problème d'automorphisme de graphe est le problème de tester si un graphe a un automorphisme non trivial. Il appartient à la classe NP de complexité de calcul. Semblable au problème d'isomorphisme de graphe, on ne sait pas s'il a un algorithme en temps polynomial ou s'il est NP-complet . Il existe un algorithme en temps polynomial pour résoudre le problème d'automorphisme de graphes pour les graphes où les degrés des sommets sont limités par une constante. Le problème d'automorphisme de graphe est polynomial à plusieurs uns réductible au problème d'isomorphisme de graphe, mais la réduction inverse est inconnue. En revanche, la dureté est connue lorsque les automorphismes sont contraints d'une certaine manière ; par exemple, déterminer l'existence d'un automorphisme sans point fixe (un automorphisme qui ne fixe aucun sommet) est NP-complet, et le problème de comptage de tels automorphismes est ♯P-complet .
Algorithmes, logiciels et applications
Bien qu'aucun algorithme en temps polynomial du pire des cas ne soit connu pour le problème général d'automorphisme de graphes, il est plutôt facile de trouver le groupe d'automorphismes (et d'imprimer un ensemble de générateurs redondants) pour de nombreux grands graphes apparaissant dans les applications. Plusieurs outils logiciels open source sont disponibles pour cette tâche, notamment NAUTY , BLISS et SAUCY . SAUCY et BLISS sont particulièrement efficaces pour les graphes clairsemés, par exemple, SAUCY traite certains graphes avec des millions de sommets en quelques secondes seulement. Cependant, BLISS et NAUTY peuvent également produire un étiquetage canonique , alors que SAUCY est actuellement optimisé pour résoudre l'automorphisme de graphes. Une observation importante est que pour un graphe sur n sommets, le groupe d'automorphisme peut être spécifié par pas plus de n-1 générateurs, et les progiciels ci-dessus sont assurés de satisfaire cette borne comme effet secondaire de leurs algorithmes (ensembles minimaux de les générateurs sont plus difficiles à trouver et ne sont pas particulièrement utiles dans la pratique). Il apparaît également que le support total (c'est-à-dire le nombre de sommets déplacés) de tous les générateurs est limité par une fonction linéaire de n , ce qui est important dans l'analyse d'exécution de ces algorithmes. Cependant, cela n'a pas été établi pour un fait, en mars 2012.
Les applications pratiques de l'automorphisme de graphes incluent le dessin de graphes et d'autres tâches de visualisation, la résolution d'instances structurées de satisfaction booléenne apparaissant dans le contexte de la vérification formelle et de la logistique . La symétrie moléculaire peut prédire ou expliquer les propriétés chimiques.
Affichage de la symétrie
Plusieurs chercheurs en dessin de graphes ont étudié des algorithmes pour dessiner des graphes de telle sorte que les automorphismes du graphe deviennent visibles comme des symétries du dessin. Cela peut être fait soit en utilisant une méthode qui n'est pas conçue autour des symétries, mais qui génère automatiquement des dessins symétriques lorsque cela est possible, ou en identifiant explicitement les symétries et en les utilisant pour guider le placement des sommets dans le dessin. Il n'est pas toujours possible d'afficher simultanément toutes les symétries du graphe, il peut donc être nécessaire de choisir quelles symétries afficher et lesquelles ne pas visualiser.
Familles de graphes définies par leurs automorphismes
Plusieurs familles de graphes sont définies en ayant certains types d'automorphismes :
- Un graphe asymétrique est un graphe non orienté avec seulement l'automorphisme trivial.
- Un graphe vertex-transitif est un graphe non orienté dans lequel chaque sommet peut être mappé par un automorphisme dans n'importe quel autre sommet.
- Un graphe transitif par arêtes est un graphe non orienté dans lequel chaque arête peut être mappée par un automorphisme dans n'importe quelle autre arête.
- Un graphe symétrique est un graphe tel que chaque paire de sommets adjacents peut être mappée par un automorphisme dans n'importe quelle autre paire de sommets adjacents.
- Un graphe transitif en distance est un graphe tel que chaque paire de sommets peut être mappée par un automorphisme dans n'importe quelle autre paire de sommets distants l'un de l'autre.
- Un graphe semi-symétrique est un graphe qui est transitif par les bords mais pas transitif par les sommets.
- Un graphe semi-transitif est un graphe qui est vertex-transitif et arête-transitif mais pas symétrique.
- Un graphe antisymétrique est un graphe orienté avec une permutation sur les sommets qui mappe les arêtes sur les arêtes mais inverse la direction de chaque arête. De plus, σ doit être une involution .
Les relations d'inclusion entre ces familles sont indiquées par le tableau suivant :
