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 útil para muchos problemas en la teoría de grafos. El grafo de Petersen recibe su nombre de Julius Petersen , quien en 1898 lo construyó para que fuera el grafo cúbico sin puente más pequeño sin coloración de tres aristas . [1] [2]
Aunque generalmente se atribuye el grafo a Petersen, en realidad había aparecido por primera vez 12 años antes, en un artículo de AB Kempe (1886). Kempe observó que sus vértices pueden representar las diez líneas de la configuración de Desargues , y sus aristas representan pares de líneas que no se encuentran en uno de los diez puntos de la configuración. [3]
Donald Knuth afirma que el gráfico de Petersen es "una configuración notable que sirve como contraejemplo para muchas predicciones optimistas sobre lo que podría ser cierto para los gráficos en general". [4]
El gráfico de Petersen también aparece en la geometría tropical . El cono sobre el gráfico de Petersen se identifica naturalmente con el espacio de módulos de las curvas tropicales racionales de cinco puntas.
.svg/1280px-Kneser_graph_KG(5,2).svg.png)
El grafo de Petersen es el complemento del grafo lineal de . También es el grafo de Kneser ; esto significa que tiene un vértice por cada subconjunto de 2 elementos de un conjunto de 5 elementos, y dos vértices están conectados por una arista si y solo si los subconjuntos de 2 elementos correspondientes están disjuntos entre sí. Como grafo de Kneser de la forma es un ejemplo de grafo impar .
Geométricamente, el grafo de Petersen es el grafo formado por los vértices y aristas del hemidodecaedro , es decir, un dodecaedro con puntos, rectas y caras opuestas identificadas entre sí.
El grafo de Petersen no es plano . Cualquier grafo no plano tiene como menores el grafo completo o el grafo bipartito completo , pero el grafo de Petersen tiene ambos como menores. El menor se puede formar contrayendo las aristas de un grafo de coincidencia perfecta , por ejemplo las cinco aristas cortas de la primera imagen. El menor se puede formar eliminando un vértice (por ejemplo el vértice central del dibujo 3-simétrico) y contrayendo una arista incidente a cada vecino del vértice eliminado.
El dibujo plano más común y simétrico del grafo de Petersen, como un pentagrama dentro de un pentágono, tiene cinco cruces. Sin embargo, este no es el mejor dibujo para minimizar los cruces; existe otro dibujo (mostrado en la figura) con solo dos cruces. Debido a que no es plano, tiene al menos un cruce en cualquier dibujo, y si se elimina una arista de cruce de cualquier dibujo, permanece no plano y tiene otro cruce; por lo tanto, su número de cruces es exactamente 2. Cada arista en este dibujo se cruza como máximo una vez, por lo que el grafo de Petersen es 1-planar . En un toro, el grafo de Petersen se puede dibujar sin cruces de aristas; por lo tanto, tiene género orientable 1.
El grafo de Petersen también puede dibujarse (con cruces) en el plano de tal forma que todas las aristas tengan la misma longitud. Es decir, es un grafo de distancia unitaria .
La superficie no orientable más simple en la que se puede incrustar el gráfico de Petersen sin cruces es el plano proyectivo . Esta es la incrustación dada por la construcción del hemidodecaedro del gráfico de Petersen (mostrada en la figura). La incrustación del plano proyectivo también se puede formar a partir del dibujo pentagonal estándar del gráfico de Petersen colocando una tapa cruzada dentro de la estrella de cinco puntas en el centro del dibujo y enrutando los bordes de la estrella a través de esta tapa cruzada; el dibujo resultante tiene seis caras pentagonales. Esta construcción forma un mapa regular y muestra que el gráfico de Petersen tiene género 1 no orientable .
El grafo de Petersen es fuertemente regular (con signatura srg(10,3,0,1)). También es simétrico , lo que significa que es transitivo por aristas y transitivo por vértices . Más fuertemente, es transitivo por 3 arcos: cada camino dirigido de tres aristas en el grafo de Petersen puede transformarse en cualquier otro camino de ese tipo mediante una simetría del grafo. [5] Es uno de los únicos 13 grafos cúbicos de distancia regular . [6]
El grupo de automorfismos del grafo de Petersen es el grupo simétrico ; la acción de sobre el grafo de Petersen se sigue de su construcción como grafo de Kneser . El grafo de Petersen es un núcleo : cada homomorfismo del grafo de Petersen consigo mismo es un automorfismo . [7] Como se muestra en las figuras, los dibujos del grafo de Petersen pueden exhibir simetría de cinco o tres vías, pero no es posible dibujar el grafo de Petersen en el plano de tal manera que el dibujo exhiba el grupo de simetría completo del grafo.
A pesar de su alto grado de simetría, el grafo de Petersen no es un grafo de Cayley . Es el grafo transitivo de vértice más pequeño que no es un grafo de Cayley. [a]
El grafo de Petersen tiene un camino hamiltoniano pero no un ciclo hamiltoniano . Es el grafo cúbico sin puente más pequeño que no tiene ciclo hamiltoniano. Es hipohamiltoniano , lo que significa que, aunque no tiene ciclo hamiltoniano, eliminar cualquier vértice lo convierte en hamiltoniano y es el grafo hipohamiltoniano más pequeño.
Como un grafo transitivo de vértice conexo finito que no tiene un ciclo hamiltoniano, el grafo de Petersen es un contraejemplo de 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értice conexos sin ciclos hamiltonianos: el grafo completo K 2 , el grafo de Petersen, el grafo de Coxeter y dos grafos derivados de los grafos de Petersen y Coxeter reemplazando cada vértice con un triángulo. [6] Si G es un grafo r-regular, 2 -conexo, con como máximo 3 r + 1 vértices, entonces G es hamiltoniano o G es el grafo de Petersen. [8]
Para ver que el grafo de Petersen no tiene ciclo hamiltoniano, considere las aristas en el corte que desconectan el 5-ciclo interno del externo. Si hay un ciclo hamiltoniano C , debe contener un número par de estas aristas. Si contiene solo dos de ellas, sus vértices finales deben ser adyacentes en los dos 5-ciclos, lo que no es posible. Por lo tanto, contiene exactamente cuatro de ellos. Suponga que la arista superior del corte no está contenida en C (todos los demás casos son iguales por simetría). De las cinco aristas en el ciclo externo, las dos aristas superiores deben estar en C , las dos aristas laterales no deben estar en C y, por lo tanto, la arista inferior debe estar en C . Las dos aristas superiores en el ciclo interno deben estar en C , pero esto completa un ciclo no abarcador, que no puede ser parte de un ciclo hamiltoniano. Alternativamente, también podemos describir los grafos 3-regulares de diez vértices que sí tienen un ciclo hamiltoniano y demostrar que ninguno de ellos es el grafo de Petersen, encontrando un ciclo en cada uno de ellos que sea más corto que cualquier ciclo en el grafo de Petersen. Cualquier grafo hamiltoniano 3-regular de diez vértices consta de un ciclo de diez vértices C más cinco cuerdas. Si cualquier cuerda conecta dos vértices a una distancia de dos o tres a lo largo de C entre sí, el grafo tiene un 3-ciclo o 4-ciclo, y por lo tanto no puede ser el grafo de Petersen. Si dos cuerdas conectan vértices opuestos de C con vértices a una distancia de cuatro a lo largo de C , hay nuevamente un 4-ciclo. El único caso restante es una escalera de Möbius formada al conectar cada par de vértices opuestos por una cuerda, que nuevamente tiene un 4-ciclo. Dado que el grafo de Petersen tiene una circunferencia de cinco, no se puede formar de esta manera y no tiene ciclo hamiltoniano.
El grafo de Petersen tiene un número cromático 3, lo que significa que sus vértices se pueden colorear con tres colores (pero no con dos), de modo que ninguna arista conecte vértices del mismo color. Tiene una coloración de lista con 3 colores, según el teorema de Brooks para coloraciones de listas.
El grafo de Petersen tiene un índice cromático de 4; para colorear los bordes se necesitan cuatro colores. Como grafo cúbico sin puente conectado con un índice cromático de cuatro, el grafo de Petersen es un snark . Es el snark más pequeño posible y fue el único snark conocido desde 1898 hasta 1946. El teorema del snark , un resultado conjeturado por WT Tutte y anunciado en 2001 por Robertson, Sanders, Seymour y Thomas, [9] establece que cada snark tiene el grafo de Petersen como un .
Además, el gráfico tiene un índice cromático fraccionario de 3, lo que demuestra que la diferencia entre el índice cromático y el índice cromático fraccionario puede ser tan grande como 1. La antigua conjetura de Goldberg-Seymour propone que esta es la brecha más grande posible.
El número de Thue (una variante del índice cromático) del gráfico de Petersen es 5.
El grafo de Petersen requiere al menos tres colores en cualquier coloración (posiblemente inapropiada) que rompa todas sus simetrías; es decir, su número distintivo es tres. A excepción de los grafos completos, es el único grafo de Kneser cuyo número distintivo no es dos. [10]
El gráfico de Petersen:
Un subgrafo euleriano de un grafo es un subgrafo que consiste en un subconjunto de las aristas de , que tocan cada vértice de un número par de veces. Estos subgrafos son los elementos del espacio de ciclos de y a veces se denominan ciclos. Si y son dos grafos cualesquiera, una función desde las aristas de hasta las aristas de se define como continua en ciclos si la preimagen de cada ciclo de es un ciclo de . Una conjetura de Jaeger afirma que todo grafo sin puente tiene una aplicación continua en ciclos al grafo de Petersen. Jaeger demostró que esta conjetura implica la conjetura de doble cobertura de 5 ciclos y la conjetura de Berge-Fulkerson. [18]
El gráfico de Petersen generalizado se forma conectando los vértices de un n -gono regular con los vértices correspondientes de un polígono estrellado con el símbolo de Schläfli { n / k }. [19] [20] Por ejemplo, en esta notación, el gráfico de Petersen es : se puede formar conectando los vértices correspondientes de un pentágono y una estrella de cinco puntas, y las aristas de la estrella conectan cada segundo vértice. Los gráficos de Petersen generalizados también incluyen el n -prisma , el gráfico de Durero , el gráfico de Möbius-Kantor , el dodecaedro , el gráfico de Desargues y el gráfico de Nauru .
La familia Petersen consta de los siete grafos que se pueden formar a partir del grafo de Petersen mediante cero o más aplicaciones de transformadas Δ-Y o Y-Δ . El grafo completo K 6 también está en la familia Petersen. Estos grafos forman los menores prohibidos para grafos incrustables sin enlaces , grafos que se pueden incrustar en el espacio tridimensional de tal manera que no haya dos ciclos en el grafo enlazados . [21]
El gráfico de Clebsch contiene muchas copias del gráfico de Petersen como subgrafos inducidos : para cada vértice v del gráfico de Clebsch, los diez no vecinos de v inducen una copia del gráfico de Petersen.
