Usuario:Jmi2k/Petersen graph

Jmi2k/Petersen graph

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. ​

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."​

Construcciones

Grafo de Petersen, representado como un grafo de Kneser $KG_{5,3}$

Simetrías

El Petersen graph es fuertemente regular (con srg(10,3,0,1)). Es también simétrico, significando que es borde transitive y vértice transitive. Más fuertemente, es 3-arc-transitive: cada dirigido camino de tres bordes en el Petersen graph puede ser transformado a cada otro tal camino por una simetría del graph.​ Es uno de única 13 distancia cúbica-regular graphs.​ [[Categoría:Grafos regulares]] [[Categoría:Grafos individuales]]