Ê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 de Petersen
Résumé
Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et .
Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886.
Donald Knuth explique dans The Art of Computer Programming que le graphe de Petersen est .
Le graphe de Petersen est le complémentaire du line graph du graphe complet . C'est également le graphe de Kneser ; il est donc possible de construire le graphe de Petersen en considérant un sommet pour chaque couple d'un ensemble de 5 éléments, et en reliant deux sommets si les couples correspondants sont disjoints.
Géométriquement, le graphe de Petersen est le graphe formé par les sommets et les arêtes de l', un dodécaèdre dont les sommets, arêtes et faces opposés sont identifiés deux à deux.
vignette|Le graphe de Petersen est un graphe de Moore. Tout parcours en largeur a d(d-1)i sommets à son ième niveau.
Le graphe de Petersen est une (3,5)-cage, c'est-à-dire un graphe minimal en nombre de sommets ayant une maille de 5 et étant cubique. Il s'agit de l'unique (3,5)-cage et sa taille coïncide avec la borne de Moore, une borne inférieure sur le nombre de sommets que peut avoir une cage. Un tel graphe est qualifié de graphe de Moore.
Le diamètre du graphe de Petersen, l'excentricité maximale de ses sommets, ainsi que son rayon, l'excentricité minimale de ses sommets, sont égaux à 2. Cela entraîne que tous ses sommets appartiennent à son centre. C'est aussi le plus grand graphe cubique de diamètre 2.
Le graphe de Petersen est 3-sommet-connexe et 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté, il faut le priver au minimum de ou de . Comme il est régulier de degré 3, ce nombre est optimal.
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.