Conde de Petersen

El gráfico de Petersen  es un gráfico no dirigido con 10 vértices y 15 aristas; un gráfico bastante simple que se usa como ejemplo y contraejemplo para muchos problemas de teoría de grafos.

Nombrado en honor a Julius Petersen , quien lo construyó en 1898 como el gráfico cúbico sin puente más pequeño que no tiene una coloración de borde de tres colores [1] . Al mismo tiempo, la primera mención de tal gráfico se observa en un artículo de 1886 de Kempe [2] , en el que se señala que sus vértices pueden considerarse como diez líneas de la configuración de Desargues , y los bordes son pares de líneas cuya intersección no pertenece a la configuración.

Donald Knuth señala que el gráfico es notable por proporcionar contraejemplos a muchas afirmaciones "optimistas" sobre los gráficos en general [3] .

El gráfico de Petersen también aparece en la geometría tropical : el cono sobre el gráfico de Petersen se identifica naturalmente por el espacio modular de curvas tropicales racionales de cinco puntos.

Edificio

El gráfico de Petersen es el complemento del gráfico de líneas para . La cuenta es también una cuenta Kneser . Esto significa que el gráfico 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 solo si los subconjuntos de 2 elementos correspondientes no se cruzan. Como gráfico de Kneser de la forma, el gráfico es un gráfico impar .

Geométricamente, un grafo de Petersen es un grafo formado por los vértices y aristas de un semidodecaedro , es decir, un dodecaedro con vértices, aristas y caras opuestas identificadas.

Adjuntos

El gráfico de Petersen no es plano . Cualquier gráfico no plano tiene un gráfico completo o un gráfico bipartito completo como menores , pero el gráfico de Petersen tiene ambos gráficos como menores. El menor se puede obtener contrayendo las aristas de un emparejamiento perfecto , por ejemplo, las cinco aristas cortas de la primera figura. Se puede obtener un menor eliminando un vértice (por ejemplo, el vértice central de un patrón de 3 simetría) y contrayendo los bordes incidentes a cada vecino del vértice eliminado.

El dibujo plano más simétrico generalmente aceptado del gráfico de Petersen como un pentágono dentro de un pentágono tiene cinco intersecciones. Sin embargo, este no es el patrón más óptimo, minimizando el número de intersecciones. Hay otro patrón (que se muestra a la derecha) con solo dos intersecciones. Por lo tanto, el gráfico de Petersen tiene el número de intersección 2. Cada borde de esta figura se cruza como máximo una vez, por lo que el gráfico de Petersen es uniplano . En un toroide , el gráfico de Petersen se puede dibujar sin bordes cruzados. Por lo tanto, el gráfico tiene género orientable 1.

El gráfico de Petersen también se puede dibujar (con intersecciones) en el plano de tal manera que todos los bordes tengan la misma longitud. Por lo tanto, el gráfico 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 intersecciones es el plano proyectivo . Esta es una incrustación que se obtiene al construir el gráfico de Petersen como un semidodecaedro . También se puede formar una incrustación en el plano proyectivo a partir del dibujo pentagonal estándar de Petersen colocando una película (una botella de Klein cortada) dentro de la estrella pentagonal en el centro del dibujo y dirigiendo los bordes de la estrella a través de esta película. El patrón 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.

Simetrías

El gráfico de Petersen es muy regular (con la firma srg(10,3,0,1)). El gráfico también es simétrico , lo que significa que es transitivo de borde y transitivo de vértice . Más estrictamente, el gráfico es transitivo de 3 arcos: cualquier camino dirigido de los tres caminos en el gráfico de Petersen se puede asignar a cualquier otro camino por simetría de gráfico [4] . El gráfico es uno de los 13 gráficos regulares de distancia cúbica . [5]

El grupo de automorfismos del gráfico de Petersen es el grupo simétrico . La acción en el gráfico de Petersen se deriva de su construcción como gráfico de Kneser . Cualquier homeomorfismo del gráfico de Petersen sobre sí mismo que no identifique vértices adyacentes es un automorfismo. Como se muestra en las ilustraciones, los dibujos del gráfico de Petersen pueden mostrar simetrías en cinco direcciones o en tres direcciones, pero no es posible dibujar un gráfico de Petersen en el plano de tal manera que el dibujo muestre la simetría completa del grupo de gráficos.

A pesar de su alta 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. [6]

Caminos y ciclos hamiltonianos

El gráfico de Petersen tiene un camino hamiltoniano pero no un ciclo hamiltoniano . Un gráfico es el gráfico cúbico no puente más pequeño que no tiene un ciclo hamiltoniano. El grafo es hipo -Hamiltoniano, lo que significa que aunque no tiene un ciclo hamiltoniano, eliminar cualquier vértice lo convierte en hamiltoniano, y es el grafo hipo-Hamiltoniano más pequeño.

Como un gráfico transitivo de vértice conectado finito sin ciclo hamiltoniano, el gráfico de Petersen es un contraejemplo de una variante de la conjetura de Lovas , pero la formulación canónica de la conjetura pide un camino hamiltoniano, y para el gráfico de Petersen esta conjetura se cumple.

Solo se conocen cinco gráficos transitivos de vértice conectados sin ciclos hamiltonianos: el gráfico K 2 completo , el gráfico de Petersen , el gráfico de Coxeter y dos gráficos obtenidos a partir de los gráficos de Petersen y Coxeter reemplazando cada vértice con un triángulo [7] . Si G es un grafo regular r conectado en 2 con un máximo de 3r  + 1 vértices, entonces G es hamiltoniano o G es un grafo de Petersen [8] .

Para mostrar que el gráfico de Petersen no tiene un ciclo hamiltoniano C , considere los bordes que conectan el ciclo interno de 5 vértices con el ciclo externo. Si existe un ciclo hamiltoniano, se debe elegir un número par de estas aristas. Si solo se seleccionan dos aristas, sus vértices finales deben ser adyacentes en ambos ciclos de 5 vértices, lo cual no es posible. Por lo tanto, se deben seleccionar 4 bordes. Suponga que el borde superior no está seleccionado (todos los demás casos son similares debido a la simetría). De los 5 bordes del ciclo exterior, los dos bordes superiores deben incluirse en el ciclo hamiltoniano, por lo que los dos bordes laterales no deben incluirse en el ciclo, y luego el borde inferior debe incluirse en el ciclo. Se deben elegir los dos bordes superiores en el ciclo interno, pero luego esos dos bordes cierran un ciclo que no está completo, por lo que no puede ser parte de un ciclo hamiltoniano. Alternativamente, podemos considerar gráficos de 3 regulares de diez vértices que tienen un ciclo hamiltoniano, y mostrar que ninguno de estos gráficos es un gráfico de Petersen al encontrar un ciclo en cada uno de ellos que sea más corto que cualquier ciclo del gráfico de Petersen. Cualquier gráfico de tres 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 lo largo de C a una distancia de dos o tres entre sí, entonces el gráfico tiene un ciclo de 3 o un ciclo de 4 y, por lo tanto, no puede ser un gráfico de Petersen. Si dos cuerdas conectan vértices opuestos de un ciclo C a una distancia de cuatro a lo largo de C , nuevamente hay un ciclo de 4. Sólo queda el caso de la escalera de Möbius , formada por la unión de cada par de lados opuestos por una cuerda, que de nuevo tiene un cuatriciclo. Dado que la circunferencia del gráfico de Petersen es cinco, no se puede formar de esta manera y, por lo tanto, no tiene un ciclo hamiltoniano.

Dibujo para colorear

El grafo de Petersen tiene el número cromático 3, lo que significa que los vértices del grafo se pueden colorear con tres colores, pero no con dos, por lo que ninguna arista une dos vértices del mismo color. El gráfico tiene una coloración prescrita de 3 colores según el teorema de Brooks para coloraciones prescritas. El gráfico de Petersen tiene un índice cromático de 4, lo que significa que la coloración de los bordes requiere cuatro colores. En otras palabras, el gráfico no es la suma de tres factores 1 , como demostró el propio Petersen [9] . Para probar esto, se deben verificar cuatro casos para mostrar que no hay 3 colores de bordes. Como un gráfico cúbico conectado sin puente con índice cromático cuatro, el gráfico de Petersen es un snark . Este gráfico es el snark más pequeño posible. Fue el único snark conocido en el período 1898-1946. El teorema del snark , expresado en la forma de la conjetura de Tutt (probada en 2001 por Robertson, Sanders, Seymour y Thomas [10] ), establece que cualquier snark tiene un gráfico de Petersen como menor .

Además, el gráfico tiene un índice cromático fraccionario de 3, lo que respalda la afirmación de que la diferencia entre el índice cromático y el índice cromático fraccionario puede ser 1. La antigua conjetura de Goldberg-Seymour sugiere que esta es la mayor diferencia 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 las simetrías. Es decir, el número de color característico del gráfico es igual a tres. A excepción de los gráficos completos, sólo existe un gráfico de Kneser cuyo número característico no es igual a dos [11] .

Otras propiedades

Conde Petersen:

• está conectado en 3 y, por lo tanto, conectado en 3 aristas y sin puente. Ver gráfico conectado .
• tiene un número de independencia de 4 y es de 3 partes. Ver Problema de conjuntos independientes .
• es un gráfico cúbico , tiene un número de dominancia de 3, tiene una coincidencia perfecta y un factor de 2 .
• tiene 6 coincidencias perfectas distintas.
• es el gráfico cúbico más pequeño con circunferencia 5. (Es el único : una celda . El gráfico tiene solo 10 vértices, por lo que es el único : un gráfico de Moore ). [12] .
• tiene radio 2 y diámetro 2. Este es el gráfico cúbico más grande con diámetro 2 [13]
• tiene el espectro gráfico −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
• tiene 2000 árboles de expansión , más que cualquier gráfico cúbico con 10 vértices [14]
• tiene un polinomio cromático [15]
• tiene un polinomio característico , lo que lo convierte en un gráfico de enteros,  un gráfico cuyo espectro consiste completamente en números enteros.
• Entre dos vértices cualesquiera hay un camino único de longitud como máximo dos.

Conjetura de coloración de Petersen

Según Devos, Nexetril y Raspo, “ El ciclo de un grafo G es un conjunto C E(G) tal que cualquier vértice del grafo (V(G),C) tiene un grado par. Si G, H son gráficos, definimos un mapeo φ: E(G) -> E(H) como ciclo continuo si la imagen previa de cualquier ciclo en H es un ciclo en G. François Jaeger formuló una conjetura que establece que cualquier gráfico sin puente tiene un mapa de ciclo continuo para el gráfico de Petersen. Jaguer demostró que si la conjetura es verdadera, entonces la conjetura del doble recubrimiento con ciclos de longitud 5 y la conjetura de Berge-Fulkerson también lo son. [16] .

Gráficos relacionados

El gráfico de Petersen generalizado G ( n , k ) se forma conectando los vértices de un n - gon regular con los vértices correspondientes de un polígono en estrella con el símbolo de Schläfli { n / k } [17] [18] . Por ejemplo, en estas notaciones, el gráfico de Petersen se denota como G (5,2): se puede formar conectando los vértices correspondientes de un pentágono y una estrella pentagonal, mientras que los vértices de la estrella están conectados a través de uno. Los gráficos de Petersen generalizados también incluyen n -prismas G ( n ,1), gráfico de Durero G (6,2), gráfico de Möbius-Cantor G (8,3), gráfico de dodecaedro G (10,2), gráfico de Desargues G (10, 3) y Conde Nauru G (12.5).

La familia de gráficos de Petersen consta de siete gráficos que se pueden formar a partir de un gráfico de Petersen aplicando cero o más transformaciones Δ-Y o Y-Δ . El gráfico completo K 6 también pertenece a la familia Petersen. Estos gráficos forman menores prohibidos para gráficos incrustables sin enlaces , gráficos que se pueden incrustar en un espacio tridimensional de tal manera que no hay dos ciclos en el gráfico vinculados [19]

El gráfico de Clebsch consta de copias del gráfico de Petersen como subgráficos generados :  para cada vértice v del gráfico de Clebsch, diez vértices no vecinos v generan una copia del gráfico de Petersen.

Notas

1. ↑ El gráfico de Petersen .
2. ↑ Kempe, 1886 .
3. ↑ Knuth, 2011 .
4. ↑ Babai, 1995 , pág. 1447-1540.
5. ↑ Según la Lista Foster .
6. ↑ Como se indicó, esto supone que los gráficos de Cayley no están necesariamente conectados. Algunas fuentes requieren que los gráficos de Cayley estén conectados, lo que hace que el gráfico vacío de dos vértices sea el gráfico transitivo de vértice más pequeño que no es un gráfico de Cayley. Por definición dada en estas fuentes, un gráfico de Petersen es el gráfico transitivo de vértice conectado más pequeño que no es un gráfico de Cayley.
7. ↑ Royle, G. "Gráficos simétricos cúbicos (El censo de Foster)". Archivado desde el original el 20 de julio de 2008.
8. ↑ Holton, Sheehan, 1993 , pág. 32.
9. ↑ Harari, 2003 , pág. 113.
10. ↑ Pegg, 2002 , pág. 1084–1086.
11. ↑ Albertson, Boutin, 2007 , pág. R20.
12. ↑ Hoffman, Singleton, 1960 , pág. 497–504.
13. ↑ Esto se deriva del hecho de que el gráfico es un gráfico de Moore, ya que el gráfico de Moore es el gráfico regular más grande posible con ese grado de vértices y diámetro ( Hoffman, Singleton 1960 ).
14. ↑ Jakobson, Rivin, 1999 ; Valdés, 1991 . Los gráficos cúbicos con 6 y 8 vértices en los que se maximiza el número de árboles de expansión son escaleras de Möbius .
15. ↑ Biggs, 1993 .
16. ↑ DeVos, Nešetřil, Raspaud, 2007 , p. 109–138.
17. ↑ Coxeter, 1950 .
18. ↑ Watkins, 1969 .
19. ↑ Bailey, 1997 , pág. 187.

Literatura

• F. Harari. Teoría de grafos. - M .: URSS , 2003. - ISBN 5-354-00301-6 .
• O. mineral . Teoría de grafos. — M .: URSS , 2008. — ISBN 978-5-397-00044-4 .
• Ed Pegg Jr. Reseña del libro: El colosal libro de las matemáticas  //  Avisos de la American Mathematical Society. - 2002. - vol. 49 , edición. 9 _ -doi : 10.1109/ TED.2002.1003756 . - .
• Rosemary A. Bailey. Encuestas en Combinatoria. - Prensa de la Universidad de Cambridge, 1997. - ISBN 978-0-521-59840-8 .
• Matt DeVos, Jaroslav Nešetřil, André Raspaud. Sobre mapas de bordes cuya inversa conserva flujos o tensiones // Teoría de grafos en París. - Basilea: Birkhäuser, 2007. - Pág. 109-138. - (Tendencias Matemáticas.). -doi : 10.1007 / 978-3-7643-7400-6_10 .
• Norman Biggs. Teoría algebraica de grafos. — 2do. - Cambridge: Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
• Laszlo Babai. Grupos de automorfismo, isomorfismo, reconstrucción // Manual de combinatoria / Ronald L. Graham, Martin Grötschel, László Lovász. - Holanda Septentrional, 1995. - T. I. Archivado el 11 de junio de 2010 en Wayback Machine .
• Alan J. Hoffman, Robert R. Singleton. Gráficos de Moore con diámetro 2 y 3  // IBM Journal of Research and Development. - 1960. - V. 5 , núm. 4 . - S. 497-504 . -doi : 10.1147/ rd.45.0497 .
• Michael O. Albertson, Debra L. Boutin. Uso de conjuntos determinantes para distinguir gráficos de Kneser  // Electronic Journal of Combinatorics. - 2007. - T. 14 , núm. 1 .
• Geoffrey Exoo, Frank Harary, Frank Harary. Los números cruzados de algunos grafos de Petersen generalizados // Mathematica Scandinavica. - 1981. - T. 48 . - S. 184-188 .
• HSM Coxeter. Configuraciones autoduales y gráficos regulares  // Boletín de la Sociedad Matemática Estadounidense  . - 1950. - Vol. 56 , edición. 5 . - Pág. 413-455 . -doi : 10.1090 / S0002-9904-1950-09407-5 .
• D. A. Holton, J. Sheehan. El gráfico de Petersen . - Prensa de la Universidad de Cambridge , 1993. - ISBN 0-521-43594-3 . -doi : 10.2277 / 0521435943 . Archivado el 8 de febrero de 2008 en Wayback Machine .
• Dmitri Jakobson, Igor Rivin. Sobre algunos problemas extremos en teoría de grafos. - 1999. - arXiv : math.CO/9907050 .
• AB Kempe. Una memoria sobre la teoría de la forma matemática // Philosophical Transactions of the Royal Society of London. - 1886. - T. 177 . - S. 1-70 . -doi : 10.1098/ rstl.1886.0002 .
• Laszlo Lovasz . Problemas y ejercicios combinatorios. — 2do. - Holanda Septentrional, 1993. - ISBN 0-444-81504-X .
• Julio Peterson. Sur le théorème de Tait // L'Intermédiaire des Mathematiciens. - 1898. - T. 5 . - S. 225-227 .
• AJ Schwenk. Enumeración de ciclos hamiltonianos en ciertos gráficos de Petersen generalizados // Journal of Combinatorial Theory . - 1989. - T. 47 , núm. 1 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
• L. Valdés. Propiedades extremas de los árboles de expansión en grafos cúbicos // Congressus Numerantium. - 1991. - T. 85 . - S. 143-160 .
• Marcos E. Watkins. Un teorema sobre los colorantes de Tait con una aplicación a los gráficos de Petersen generalizados // Revista de teoría combinatoria . - 1969. - T. 6 , núm. 2 . - S. 152-164 . -doi : 10.1016 / S0021-9800(69)80116-X .
• Donald E. Knuth . Un borrador de la sección 7: Introducción a la búsqueda combinatoria // El arte de la programación informática . - V. 4, prefascículo 0A.
  • Donald E. Knuth . Algoritmos combinatorios, Parte 1. - Upper Saddle River, Nueva Jersey: Addison-Wesley, 2011. - ISBN 0-201-03804-8 .
  • Donald E. Knuth . Capítulo 7: Búsqueda combinatoria // El arte de la programación. — Moscú, San Petersburgo, Kyiv: I.D. Williams, 2013. - V. 4, A/ Algoritmos Combinatorios, Parte 1. - ISBN 978-5-8459-1744-7 BBC 32.973.26-18.2.75.

Enlaces

• Keller, Mitch. Gráficos de Kneser Archivado el 5 de mayo de 2018 en Wayback Machine PlanetMath
• Weisstein, Eric W. Petersen Graph  (inglés) en el sitio web de Wolfram MathWorld .
• Gráfico de Petersen en Encyclopedia of Integer Sequences