Ê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
Graphe symétrique
Résumé
En théorie des graphes, un graphe non orienté G=(V,E) est symétrique (ou arc-transitif) si, étant donné deux paires quelconques de sommets reliés par une arête u1—v1 et u2—v2 de G, il existe un automorphisme de graphe :
tel que
et .
En d'autres termes, un graphe est symétrique si son groupe d'automorphismes agit transitivement sur ses paires ordonnées de sommets reliés. Un tel graphe est parfois appelé 1-arc-transitif.
Par définition, un graphe symétrique sans sommet isolé est sommet-transitif et arête-transitif. La distinction entre arête-transitif et arc-transitif est subtile: « Arête-transitif » signifie que pour toute paire d'arêtes et , il existe un automorphisme qui envoie l'une sur l'autre, donc tel que , alors que « arc-transitif » demande qu'en plus et que, pour un autre automorphisme , on ait . Si un graphe est arête-transitif sans être 1-transitif, alors toute arête peut être envoyée sur toute autre, mais seulement d'une seule parmi les deux façons possibles.
Le terme « symétrique » est d'ailleurs parfois employé pour désigner un graphe qui soit simplement arête-transitif et sommet-transitif ; cette utilisation du terme est ambiguë, car il existe des graphes qui sont arête-transitifs et sommet-transitifs sans être arc-transitifs. Ces graphes sont rares : le plus petit exemple est le graphe de Doyle.
Dans les cas des graphes de degré impair, un graphe arête-transitif et sommet-transitif est cependant nécessairement arc-transitif.
Un graphe cubique est un graphe régulier dont tous les sommets sont de degré 3. Les graphes cubiques symétriques sont les premiers graphes réguliers symétriques intéressants, le cas régulier de degré 2 étant trivial et se résumant aux graphes cycles.
Les graphes cubiques symétriques sont catalogués par Ronald M. Foster à partir de 1934. En 1988 un livre écrit par Ronald M. Foster, I.Z. Bouwer, W.W. Chernoff, B. Monson et Z. Star est publié contenant une liste, alors jugée exhaustive de tous les graphes cubiques symétriques jusqu'à l'ordre 512.
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.