Gráfico 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 pequeño gráfico 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 puente más pequeño sin coloración de tres bordes.

Aunque el gráfico generalmente se atribuye a Petersen, de hecho apareció por primera vez 12 años antes, en un artículo de A. B. 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.

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

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.

Construcciones

Petersen gráfico como Kneser gráfico KG5,2{displaystyle KG_{5,2}

El gráfico Petersen es el complemento del gráfico de línea K5{displaystyle K_{5}. También es el gráfico Kneser KG5,2{displaystyle KG_{5,2}; 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 un borde si y sólo si los subconjuntos de 2 elementos correspondientes se descomponen entre sí. Como gráfico Kneser de la forma KG2n− − 1,n− − 1{displaystyle KG_{2n-1,n-1} es un ejemplo de un gráfico extraño.

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

Incrustaciones

El gráfico Petersen no es plano. Cualquier gráfico no plano tiene como menores o bien el gráfico completo K5{displaystyle K_{5}, o el gráfico bipartito completo K3,3{displaystyle K_{3,3}, pero el gráfico Petersen tiene tanto como menores. El K5{displaystyle K_{5} menor se puede formar mediante la contratación de los bordes de una combinación perfecta, por ejemplo los cinco bordes cortos en la primera imagen. El K3,3{displaystyle K_{3,3} menor se puede formar eliminando un vértice (por ejemplo el vértice central del dibujo simétrico 3) y contratando un incidente de borde a cada vecino del vértice eliminado.

El gráfico Petersen tiene el cruce número 2 y es 1 plano.

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 solo 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 borde de este dibujo se cruza como máximo una vez, por lo que el gráfico de Petersen es uniplano. 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 Petersen es un gráfico de distancia unitaria: se puede dibujar en el plano con cada borde que tiene longitud unitaria.

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 un gráfico de unidad de distancia.

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 hemi-dodecaedro 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 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 gráfico Petersen y el mapa asociado incrustado en el plano proyectivo. Se identifican puntos opuestos en el círculo, dando una superficie cerrada del género no deseable 1.

Simetrías

El gráfico de Petersen es muy regular (con la firma srg(10,3,0,1)). También es simétrico, lo que significa que es transitivo de borde 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 de este tipo mediante una simetría del gráfico. Es uno de los 13 gráficos regulares de distancia cúbica.

El grupo automorfismo del gráfico Petersen es el grupo simétrico S5{displaystyle S_{5}; la acción de S5{displaystyle S_{5} en el gráfico Petersen sigue de su construcción como un gráfico Kneser. El gráfico Petersen es un núcleo: cada homomorfismo del gráfico Petersen es un automorfismo. Como se muestra en las figuras, los dibujos del gráfico Petersen pueden exhibir simetría de cinco o tres vías, pero no es posible dibujar el gráfico Petersen en el plano de tal manera que el dibujo exhiba el grupo de simetría completa 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értice más pequeño que no es un gráfico de Cayley.

Caminos y ciclos hamiltonianos

El gráfico Petersen es hipo-Hamiltoniano: eliminando cualquier vértice, como el vértice central en el dibujo, el gráfico restante es Hamiltonian. Este dibujo con la simetría orden-3 es el dado por Kempe (1886).

El gráfico de Petersen tiene un camino hamiltoniano 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 un ciclo hamiltoniano, eliminar cualquier vértice lo convierte en hamiltoniano y es el gráfico hipohamiltoniano más pequeño.

Como un gráfico transitivo de vértice conexo finito 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 solicita una ruta hamiltoniana y se verifica mediante la gráfica de Petersen.

Solo se conocen cinco gráficos transitivos de vértice conectados sin ciclos hamiltonianos: el gráfico completo K₂, el gráfico de Petersen, el gráfico de Coxeter y dos gráficos derivados del Gráficos de Petersen y Coxeter reemplazando cada vértice con un triángulo. Si G es un grafo regular r conectado por 2 con un máximo de 3r + 1 vértices, entonces G es hamiltoniano o G es el gráfico de Petersen.

Para ver que el gráfico de Petersen no tiene un ciclo hamiltoniano C, considere los bordes en el corte que desconectan el ciclo de 5 interno del externo. Si existe un ciclo hamiltoniano, se debe elegir un número par de estas aristas. Si solo se eligen dos de ellos, sus vértices finales deben ser adyacentes en los dos ciclos de 5, lo cual no es posible. Por lo tanto, se eligen 4 de ellos. Suponga 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 en el ciclo interno, pero esto completa un ciclo sin expansión, que no puede ser parte de un ciclo hamiltoniano. Alternativamente, también podemos describir los gráficos de 3 regulares de diez vértices que tienen un ciclo hamiltoniano y mostrar que ninguno de ellos es el gráfico de Petersen, encontrando un ciclo en cada uno de ellos que sea más corto que cualquier ciclo en el gráfico de Petersen. Cualquier gráfico de 3 regulares hamiltoniano 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 gráfico tiene un ciclo de 3 o de 4 ciclos y, por lo tanto, no puede ser el gráfico 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 cuatriciclo. El único caso que queda es una escalera de Möbius formada conectando cada par de vértices opuestos por una cuerda, que nuevamente tiene un ciclo de 4. Dado que el gráfico de Petersen tiene una circunferencia cinco, no se puede formar de esta manera y no tiene un ciclo hamiltoniano.

Colorear

Una 4coloración de los bordes del gráfico Petersen

Un 3 colores de los vértices del gráfico Petersen

El gráfico de Petersen tiene el 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 vértices del mismo color. Tiene una lista para colorear con 3 colores, de Brooks' teorema para la coloración 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 sarcasmo. 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, establece que cada snark tiene el gráfico de Petersen como menor de edad

Además, el gráfico tiene un índice cromático fraccional de 3, lo que demuestra que la diferencia entre el índice cromático y el índice cromático fraccional 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 incorrecta) que rompa todas sus simetrías; es decir, su número distintivo es tres. A excepción de los gráficos completos, es el único gráfico de Kneser cuyo número distintivo no es dos.

Otras propiedades

El gráfico de Petersen:

• es 3-conectado y por lo tanto 3-edge-connected y sin puente. Vea el glosario.
• tiene independencia número 4 y es 3-partito. Vea el glosario.
• es cúbico, tiene la dominación número 3, y tiene una combinación perfecta y un 2-factor.
• tiene 6 coincidencias perfectas distintas.
• es el gráfico cúbico más pequeño de circunferencia 5. (Es el único ()3,5){displaystyle (3,5)}- jaula. De hecho, ya que tiene sólo 10 vértices, es el único ()3,5){displaystyle (3,5)}- Gráfico de color.)
• es el gráfico cúbico más pequeño con Colin de Verdière gráfico invariante μ = 5.
• es el gráfico más pequeño del policía número 3.
• tiene radio 2 y diámetro 2. Es el gráfico cúbico más grande con diámetro 2.
• tiene 2000 árboles azotados, la mayor parte de cualquier gráfico cúbico de 10 vertidos.
• tiene polinomio cromático t()t− − 1)()t− − 2)()t7− − 12t6+67t5− − 230t4+529t3− − 814t2+775t− − 352){displaystyle t(t-1)(t-2)left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352right)}.
• tiene un polinomio característico ()t− − 1)5()t+2)4()t− − 3){displaystyle (t-1)^{5}(t+2)^{4}(t-3), convirtiéndolo en un gráfico integral, un gráfico cuyo espectro consiste enteramente en enteros.

Conjetura de coloración de Petersen

An Subgrafo de Euleria de un gráfico G{displaystyle G. es un subgrafo que consiste en un subconjunto de los bordes de G{displaystyle G., tocar cada vértice de G{displaystyle G. un número de veces. Estos subgrafos son los elementos del espacio del ciclo de G{displaystyle G. y a veces se llaman ciclos. Si G{displaystyle G. y H{displaystyle H. son dos gráficos, una función de los bordes de G{displaystyle G. a los bordes de H{displaystyle H. se define como ciclo continuo si la imagen previa de cada ciclo de H{displaystyle H. es un ciclo de G{displaystyle G.. Una conjetura de Jaeger afirma que cada gráfico sin puente tiene un mapeo continuo de ciclo al gráfico Petersen. Jaeger mostró esta conjetura implica la conjetura doble de 5 ciclos y la conjetura Berge-Fulkerson".

Gráficos relacionados

La familia Petersen.

El gráfico generalizado Petersen G()n,k){displaystyle G(n,k)} se forma conectando los vértices de un n-gon regular a los vértices correspondientes de un polígono estrella con el símbolo Schläfli {n/k}. Por ejemplo, en esta notación, el gráfico Petersen es G()5,2){displaystyle G(5,2)}: se puede formar conectando los vértices correspondientes de un pentágono y una estrella de cinco puntos, y los bordes de la estrella conectan cada segundo vértice. Los gráficos generalizados de Petersen también incluyen los n-prisma G()n,1){displaystyle G(n,1)} el gráfico Dürer G()6,2){displaystyle G(6,2)}, el gráfico Möbius-Kantor G()8,3){displaystyle G(8,3)}, el dodecaedro G()10,2){displaystyle G(10,2)}, el gráfico de Desargues G()10,3){displaystyle G(10,3)} y el gráfico de Nauru G()12,5){displaystyle G(12,5)}.

La familia de 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₆ también está en la familia Petersen. Estos gráficos forman los menores prohibidos para los gráficos incrustables sin enlaces, gráficos que se pueden incrustar en el espacio tridimensional de tal manera que no hay dos ciclos en el gráfico vinculados.

El gráfico de Clebsch contiene muchas copias del gráfico de Petersen como subgráficos 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.