Grafo de Petersen
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]
| 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 | |
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]
Características
- Es un grafo regular de grado 3.
- Dos vértices adyacentes no tienen vecinos en común, pero, no es bipartito, pues existen varios ciclos de longitud impar.
- Dos vértices no adyacentes tienen exactamente un vecino en común.
Equivalencias
El grafo de Petersen no es plano. Cualquier grafo no plano tiene como menores o al grafo completo o al grafo bipartito completo , pero el grafo de Petersen tiene a ambos como menores. El menor se puede format contrayendo las aristas de un apareamiento perfecto, por ejemplo las cinco aristas cortas de la primera imagen. El menor se puede format eliminando un vértice (por ejemplo el vértice central de la representación 3-simétrica) y contrayendo una arista incidente a cada vecino del vértice eliminado. La representación planar simétrica más común del grafo de Petersen (como un pentagrama contenido en un pentágono) se cruza cinco veces. Sin embargo, esta no es la mejor representación para ahorrar cruces; existe otra representación (la expuesta en la imagen siguiente) con tan sólo dos cruces. Como no es planar, tiene al menos un cruce en cualquier representación, y el número mínimo de cruces en cualquier representación es exactamente 2. El grafo de Peterson también se puede dibujar en el plano de forma que todas las aristas tengan igual longitud. Es por tanto un grafo de distancia unidad. La superficie no orientable más simple en la cual el grafo de Petersen puede ser incrustado es el plano proyectivo.
Simetrías
El grafo de Petersen es fuertemente regular. Es también simétrico, por lo que es arista-transitivo y vértice-transitivo. En concreto, es 3-arco-transitivo: todo camino dirigido de tres aristas en el grafo de Petersen puede ser transformado en cualquier otro camino similar por una simetría del grafo. El grupo automórfico del grafo de Petersen es el grupo simétrico : la acción de en el grafo de Petersen surge de su construcción como un Grafo de Kneser. Todo homomorfismo del grafo de Petersen a sí mismo que no identifica vértices adyacentes es un automorfismo. Como se puede observar en las figuras, las representaciones del grafo de Petersen pueden mostrar 5-simetría o 3-simetría, pero no se puede dibujar el grafo de Petersen en el plano de forma que la representación posea el grupo de simetría completo del grafo. A pesar de su alto grado de simetría, el grafo de Petersen no es un grupo de Cayley. Es el grafo vértice-transitivo más pequeño que no es un grupo de Cayley.
Ciclos y caminos hamiltonianos
El grafo de Petersen tiene un camino hamiltoniano pero no un ciclo hamiltoniano. Es el grafo cúbico sin puente más pequeño sin ciclo hamiltoniano. Es hipoamiltoniano, lo que significa que aunque no tiene un ciclo hamiltoniano, al eliminar cualquier vértice se convierte en hamiltoniano, y es el grafo hipoamiltoniano más pequeño.
Como un grafo finito conectado vértice-transitivo que no tiene un ciclo Hamiltoniano, el gráfico Petersen es un contra-ejemplo a una variante de la conjetura de Lovász, pero la formulación canónica de la conjetura pide un camino Hamiltoniano y es verificada por el grafo de Petersen.
Sólo se conocen cinco grafos transitivos de vértices conectados sin ciclos hamiltonianos: el grafo completo K2, el grafo de Petersen, el grafo de Coxeter y dos grafos derivados de los grafso de Petersen y Coxeter sustituyendo cada vértice por un triángulo. Si G es un grafo r-regular conectado a dos vértices, con un máximo de 3r + 1, entonces G es hamiltoniano o G es el grafo de Petersen.
Para ver que el grafo de Petersen no tiene un ciclo C hamiltoniano, considere los bordes en el corte desconectando el ciclo interno de 5 ciclos del externo. Si hay un ciclo hamiltoniano, se debe elegir un número par de estos bordes. Si sólo se eligen dos de ellos, sus vértices finales deben estar adyacentes en los dos 5 ciclos, lo que no es posible. De ahí que se hayan elegido 4 de ellos. Supongamos que no se elige el borde superior del corte (todos los demás casos son iguales por simetría). De los 5 bordes del ciclo exterior, se deben elegir los dos bordes superiores, no se deben elegir los dos bordes laterales y, por lo tanto, se debe elegir el borde inferior. Los dos bordes superiores del ciclo interior deben ser elegidos, pero esto completa un ciclo no expansivo, que no puede ser parte de un ciclo hamiltoniano. Alternativamente, también podemos describir las gráficas de diez vértices y 3-regulares que sí tienen un ciclo hamiltoniano y mostrar que ninguna de ellas es el grafo de Petersen, encontrando un ciclo en cada una de ellas que es más corto que cualquier ciclo en el grafo de Petersen. Cualquier grafo tridimensional de diez versículos hamiltonianos consta de un ciclo de diez versículos C más cinco cuerdas. Si alguna cuerda conecta dos vértices a una distancia de dos o tres a lo largo de C uno del otro, el grafo tiene un ciclo de 3 o 4 ciclos, y por lo tanto no puede ser el grafo de Petersen. Si dos cuerdas conectan vértices opuestos de C a vértices a una distancia de cuatro a lo largo de C, hay de nuevo un ciclo de 4. El único caso que queda es una escalera Möbius formada por la conexión de cada par de vértices opuestos por una cuerda, que de nuevo tiene un ciclo de 4. Dado que el grafo de Petersen tiene una circunferencia de cinco, no puede formarse de esta manera y no tiene un ciclo hamiltoniano.
Coloración
El grafo de Petersen tiene el número cromático 3, lo que significa que sus vértices pueden ser coloreados con tres colores (pero no con dos) de manera que ningún borde conecte vértices del mismo color. Tiene una lista de coloración formada por 3 colores, según el teorema de Brooks.
El grafo de Petersen tiene un índice cromático 4; la coloración de los bordes requiere cuatro colores. Como un grafo cúbico sin puente conectado con índice cromático cuatro, el grafo de Petersen es un snark. Es el snark más pequeño posible, y fue el único conocido desde 1898 hasta 1946. El teorema del snark, conjeturado por W. T. Tutte y anunciado en 2001 por Robertson, Sanders, Seymour y Thomas, afirma que cada snark tiene el grafo de Petersen como un menor.
Además, el grafo tiene un índice cromático fraccionario 3, lo que demuestra que la diferencia entre el índice cromático y el índice cromático fraccionario puede ser tan grande como 1.
El número Thue (una variante del índice cromático) del grafo de Petersen es 5.
El grafo de Petersen requiere al menos tres colores en cualquier coloración que rompa todas sus simetrías; es decir, su número distintivo es tres. Excepto en los gráficos completos, que son los únicos grafo de Kneser cuyo número distintivo no es dos.
La conjetura de coloración de Petersen
Según DeVos, Nesetril y Raspaud, "Un ciclo de un grafo G es un conjunto C E(G) para que cada vértice del gráfico (V(G),C) tenga un grado parecido. Si G,H son grafos, definimos un mapa φ: E(G) -> E(H) que sea ciclo continuo si la pre-imagen de cada ciclo de H es un ciclo de G. Una fascinante conjetura de Jaeger afirma que cada gráfico sin puente tiene un ciclo continuo de mapeo al grafo de Petersen. Jaeger demostró que si esta conjetura es cierta, entonces también lo son la conjetura de 5 ciclos de doble cubierta y la conjetura de Berge-Fulkerson".
Grafos relacionados
El grafo generalizado de Petersen G(n,k) se forma conectando los vértices de un polígono regular de n lados a los vértices correspondientes de una estrella con el símbolo de Schläfli {n/k}.[3] Por ejemplo, en esta notación, el grafo de Petersen es G(5,2): puede formarse conectando los vértices correspondientes de un pentágono y una estrella de cinco puntas, y los bordes de la estrella conectan cada dos vértices. Los grafos generalizados de Petersen también incluyen el prisma-n G(n,1), el grafo de Dürer G(6,2), el grafo de Möbius-Kantor G(8,3), el dodecaedro G(10,2), el grafo de Desargues G(10,3) y el grafo de Nauru G(12,5).
La familia Petersen está formada por los siete grafos que pueden ser formados a partir del grafo Petersen por cero o más aplicaciones de transformaciones Δ-Y o Y-Δ. El grafo completo K6 también pertenece a la familia Petersen.
El grafo de Clebsch contiene muchas copias del grafo de Petersen como subgrafos inducidos: por cada vértice v del grafo de Clebsch, los diez no vecinos de v inducen una copia del grafo de Petersen.
Referencias
- 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.
- Coxeter (1950); Watkins (1969).