Back Graf de Petersen Catalan Petersenův graf Czech Petersen-Graph German Petersen graph English Peterseni graaf Estonian گراف پترسن Persian Graphe de Petersen French Petersenov graf Croatian Petersen-gráf Hungarian Graf Petersen ID
| Grafo de Petersen | ||
|---|---|---|
 El grafo de Petersen es comúnmente dibujado como un pentágono con una estrella de 5 puntas dentro. | ||
| Nombre en honor a | Julius Petersen | |
| Vértices | 10 | |
| Aristas | 15 | |
| Radio | 2 | |
| Diámetro | 2 | |
| Cintura | 5 | |
| Automorfismos | 120 (S5) | |
| Número cromático | 3 | |
| Índice cromático | 4 | |
| Propiedades |
Cúbico Fuertemente regular Distancia transitiva Snark | |
En el campo matemático de la teoría de grafos, el grafo de Petersen es un grafo no dirigido con 10 vértices y 15 aristas . Es un grafo pequeño que sirve como ejemplo y contraejemplo para muchos problemas en la teoría de grafos. El grafo de Petersen lleva el nombre de Julius Petersen, quien en 1898 lo construyó para ser el grafo cúbico sin puentes más pequeño que no se puede 3-colorear.[1]
Aunque comúnmente se le da crédito a Petersen, en realidad apareció por primera vez 12 años antes, en un artículo de A. B. Kempe. Kempe observó que sus vértices pueden representar las diez líneas de la configuración de Desargues, y sus bordes representan pares de líneas que no se encuentran en uno de los diez puntos de la configuración.
Donald Knuth afirma que el grafo de Petersen es "una configuración notable que sirve como contraejemplo a muchas predicciones optimistas sobre qué podría ser cierto en un grafo en general."[2]
- ↑ Brouwer, Andries E., The Petersen graph.
- ↑ Knuth, Donald E., The Art of Computer Programming; volumen 4, pre-fascículo 0A (en inglés). A draft of section 7: Introduction to combinatorial searching.