En el campo matemático de la teoría de grafos , el gráfico de Petersen es un gráfico no dirigido con 10 vértices y 15 aristas . Es un gráfico pequeño que sirve como ejemplo y contraejemplo útil para muchos problemas de teoría de grafos. El gráfico de Petersen lleva el nombre de Julius Petersen , quien en 1898 lo construyó para que fuera el gráfico cúbico sin puentes más pequeño y sin coloración de tres aristas. [1] [2]
Aunque generalmente se atribuye el mérito del gráfico a Petersen, de hecho 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 de muchas predicciones optimistas sobre lo que podría ser cierto para los gráficos en general". [4]
El gráfico de Petersen también hace acto de presencia 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)
La gráfica de Petersen es el complemento de la gráfica lineal de . Es también el gráfico de Kneser ; esto significa que tiene un vértice para cada subconjunto de 2 elementos de un conjunto de 5 elementos, y dos vértices están conectados por una arista si y sólo si los correspondientes subconjuntos de 2 elementos están separados entre sí. Como gráfico de Kneser de la forma , es un ejemplo de gráfico impar .
Geométricamente, el gráfico de Petersen es el gráfico formado por los vértices y aristas del hemidodecaedro , es decir, un dodecaedro con puntos, rectas y caras opuestas identificadas entre sí.
La gráfica de Petersen no es plana . Cualquier grafo no plano tiene como menores el grafo completo o el grafo bipartito completo , pero el grafo de Petersen tiene a ambos como menores. El menor se puede formar contrayendo los bordes de una combinación perfecta , por ejemplo los cinco bordes cortos en la primera imagen. El menor se puede formar eliminando un vértice (por ejemplo, el vértice central del dibujo trisimétrico) y contrayendo un borde incidente con cada vecino del vértice eliminado.
El dibujo plano más común y simétrico del gráfico 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 (que se muestra en la figura) con sólo dos cruces. Debido a que no es plano, tiene al menos un cruce en cualquier dibujo, y si se elimina un borde de cruce de cualquier dibujo, permanece no plano y tiene otro cruce; por lo tanto, su número de cruce es exactamente 2. Cada arista en este dibujo se cruza como máximo una vez, por lo que la gráfica de Petersen es uniplanar . En un toro, el gráfico de Petersen se puede dibujar sin cruces de aristas; por lo tanto tiene género orientable 1.
El gráfico de Petersen también se puede dibujar (con cruces) en el plano de tal manera que todas las aristas tengan la misma longitud. Es decir, es una gráfica 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 hemidodecaedro del gráfico de Petersen (que se muestra 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 cruz dentro de la estrella de cinco puntas en el centro del dibujo y pasando los bordes de la estrella a través de esta cruz; 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 gráfico de Petersen es fuertemente regular (con firma srg(10,3,0,1)). También es simétrico , lo que significa que es transitivo de arista y transitivo de vértice . Más fuertemente, es transitivo de 3 arcos: cada camino dirigido de tres aristas en el gráfico de Petersen se puede transformar en cualquier otro camino mediante una simetría del gráfico. [5] Es uno de los 13 gráficos cúbicos de distancia regular . [6]
El grupo de automorfismos del gráfico de Petersen es el grupo simétrico ; la acción de en el gráfico de Petersen se deriva de su construcción como gráfico de Kneser . El gráfico de Petersen es un núcleo : cada homomorfismo del gráfico de Petersen consigo mismo es un automorfismo. [7] Como se muestra en las figuras, los dibujos del gráfico de Petersen pueden exhibir simetría de cinco o tres vías, pero no es posible dibujar el gráfico de Petersen en el plano de tal manera que el dibujo exhiba la simetría completa. grupo del gráfico.
A pesar de su alto grado de simetría, el gráfico de Petersen no es un gráfico de Cayley . Es el gráfico transitivo de vértices más pequeño que no es un gráfico de Cayley. [a]
El gráfico de Petersen tiene una trayectoria hamiltoniana pero no un ciclo hamiltoniano . Es el gráfico cúbico sin puente más pequeño sin ciclo hamiltoniano. Es hipohamiltoniano , lo que significa que aunque no tiene ciclo hamiltoniano, eliminar cualquier vértice lo convierte en hamiltoniano y es el gráfico hipohamiltoniano más pequeño.
Como gráfico transitivo de vértice finito conectado que no tiene un ciclo hamiltoniano, el gráfico 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 gráfico de Petersen.
Sólo se conocen cinco gráficos transitivos de vértices conectados sin ciclos hamiltonianos: el gráfico completo K 2 , el gráfico de Petersen, el gráfico de Coxeter y dos gráficos derivados de los gráficos de Petersen y Coxeter reemplazando cada vértice con un triángulo. [6] Si G es un gráfico r -regular biconexo con como máximo 3 r + 1 vértices, entonces G es hamiltoniano o G es el gráfico de Petersen. [8]
Para ver que el gráfico de Petersen no tiene un ciclo hamiltoniano C , considere los bordes en el corte que desconectan el 5 ciclo interno del externo. Si hay un ciclo hamiltoniano, se debe elegir un número par de estas aristas. Si sólo se eligen dos de ellos, sus vértices finales deben ser adyacentes en los dos 5 ciclos, lo cual no es posible. Por lo tanto se eligen 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. Se deben elegir los dos bordes superiores del ciclo interno, pero esto completa un ciclo que no se extiende, que no puede ser parte de un ciclo hamiltoniano. Alternativamente, también podemos describir las gráficas de 3 regulares de diez vértices que tienen un ciclo hamiltoniano y mostrar que ninguna de ellas es la gráfica de Petersen, encontrando un ciclo en cada una de ellas que sea más corta que cualquier ciclo en la gráfica de Petersen. Cualquier gráfico hamiltoniano 3-regular de diez vértices consta de un ciclo C de diez vértices 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í, la gráfica tiene un ciclo de 3 o 4 ciclos y, por lo tanto, no puede ser la gráfica de Petersen. Si dos cuerdas conectan vértices opuestos de C con vértices a una distancia cuatro a lo largo de C , nuevamente hay un ciclo de 4. El único caso restante es una escalera de Möbius formada conectando cada par de vértices opuestos mediante una cuerda, que nuevamente tiene 4 ciclos. Dado que el gráfico de Petersen tiene circunferencia cinco, no se puede formar de esta manera y no tiene ciclo hamiltoniano.
El gráfico de Petersen tiene 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 ningún borde conecte los vértices del mismo color. Tiene una coloración de listas con 3 colores, según el teorema de Brooks para coloraciones de listas.
El gráfico de Petersen tiene índice cromático 4; colorear los bordes requiere cuatro colores. Como gráfico cúbico sin puente conectado con índice cromático cuatro, el gráfico de Petersen es un sarcástico . Es el snark más pequeño posible y fue el único snark conocido desde 1898 hasta 1946. El teorema de snark , un resultado conjeturado por WT Tutte y anunciado en 2001 por Robertson, Sanders, Seymour y Thomas, [9] afirma que todo snark tiene el gráfico de Petersen como menor .
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 gráfico de Petersen requiere al menos tres colores en cualquier coloración (posiblemente inadecuada) que rompa todas sus simetrías; es decir, su número distintivo es el tres. A excepción de los gráficos completos, es el único gráfico de Kneser cuyo número distintivo no es dos. [10]
El gráfico de Petersen:
Un subgrafo euleriano de un gráfico es un subgrafo que consta de un subconjunto de aristas de , que tocan cada vértice de un número par de veces. Estos subgrafos son los elementos del espacio de ciclos y a veces se les llama ciclos. Si y son dos gráficos cualesquiera, una función desde los bordes de hasta los bordes de se define como continua de ciclo si la imagen previa de cada ciclo de es un ciclo de . Una conjetura de Jaeger afirma que todo gráfico sin puente tiene un mapeo de ciclo continuo con el gráfico de Petersen. Jaeger demostró que esta conjetura implica la conjetura de la doble cobertura de 5 ciclos y la conjetura de Berge-Fulkerson." [17]
El gráfico de Petersen generalizado se forma conectando los vértices de un n -gón regular a los vértices correspondientes de un polígono estrella con el símbolo de Schläfli { n / k }. [18] [19] 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 los bordes de la estrella conectan cada segundo vértice. Los gráficos generalizados de Petersen 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 siete gráficos que se pueden formar a partir del gráfico de Petersen mediante cero o más aplicaciones de transformadas Δ-Y o Y-Δ . El gráfico completo K 6 también pertenece a la familia Petersen. Estos gráficos forman los menores prohibidos para los gráficos integrables sin vínculos , gráficos que se pueden incrustar en un espacio tridimensional de tal manera que no haya dos ciclos en el gráfico vinculados . [20]
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.
