Graphe de Petersen
graphe cubique possédant 10 sommets et 15 arêtes / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Graphe de Petersen?
Résumez cet article pour un enfant de 10 ans
Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant 10 sommets et 15 arêtes.
Graphe de Petersen | |
Schéma classique du graphe de Petersen, sous la forme d'un pentagone et d'un pentagramme concentriques, reliés par cinq rayons. | |
Nombre de sommets | 10 |
---|---|
Nombre d'arêtes | 15 |
Distribution des degrés | 3-régulier |
Rayon | 2 |
Diamètre | 2 |
Maille | 5 |
Automorphismes | 120 (S5) |
Nombre chromatique | 3 |
Indice chromatique | 4 |
Propriétés | Cage Cubique Distance-transitif Distance-unité Fortement régulier Hypohamiltonien Graphe de Moore Snark Symétrique |
modifier |
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[1]. Il a cependant été mentionné par Alfred Kempe pour la première fois 12 ans auparavant, en 1886[2].
Donald Knuth explique dans The Art of Computer Programming que le graphe de Petersen est « une configuration remarquable qui sert de contre-exemple à de nombreuses prédictions optimistes sur ce qui devrait être vrai pour tous les graphes[3] ».