Ê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 GraphSearch.
Concept
Graphe de Petersen généralisé
Résumé
vignette| Le graphe de Dürer G (6, 2).
En théorie des graphes, les graphes de Petersen généralisés sont une famille de graphes cubiques formés en connectant les sommets d'un polygone régulier aux sommets correspondants d'un polygone régulier étoilé. Ils comprennent le graphe de Petersen et généralisent l'une des manières de construire le graphe de Petersen. La famille des graphes de Petersen généralisés a été introduite en 1950 par H. S. M. Coxeter et a reçu son nom en 1969 par Mark Watkins.
Dans la notation introduite par Watkins, G(n,k) est un graphe avec un ensemble de 2n sommets
et ensemble d'arêtes
où les indices sont modulo n et k < n /2. Certains auteurs utilisent la notation GPG(n,k). La notation de Coxeter pour le même graphe est {n} + {n/k} ; c'est une combinaison des symboles de Schläfli pour le polygone régulier et pour le polygone régulier étoilé à partir desquels le graphe est formé. Le graphe de Petersen lui-même est le graphe G(5,2), resp. {5} + {5/2}.
Tout graphe de Petersen généralisé peut également être construit à partir d'un avec deux sommets, deux boucles et une autre arête.
Parmi les graphes de Petersen généralisés il y a les graphes prismatiques G(n,1), le graphe de Dürer G(6,2), le graphe de Möbius-Kantor G(8, 3), le dodécaèdre G(10,2), le graphe de Desargues G(10,3) et le graphe de Nauru G(12,5).
Quatre graphes de Petersen généralisés, à savoir le 3-prisme, le 5-prisme, le graphe de Dürer et G(7,2), font partie des sept graphes cubiques, 3-sommet-connexes et « bien couverts » (ce qui signifie que tous leurs ensembles indépendants maximaux ont même taille).
vignette| L'un des trois cycles hamiltoniens de G(9,2). Les deux autres cycles hamiltoniens du même graphe sont symétriques dans des rotations de 40° du dessin.
La famille des graphes de Petersen généralisés possède un certain nombre de propriétés remarquables, parmi lesquelles les suivantes :
G(n,k) est sommet-transitif (ce qui signifie qu'il a des automorphismes qui envoient tout sommet sur tout autre sommet) si et seulement si (n,k) = (10, 2) ou k2 ≡ ±1 (mod n ).
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.