stringtranslate.com

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

Construcciones

Gráfico de Petersen como gráfico de Kneser

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

Incrustaciones

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 gráfico de Petersen tiene el número de cruce 2 y es 1-planar .

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 gráfico de Petersen es un gráfico de distancia unitaria : se puede dibujar en el plano con cada borde con una longitud unitaria.

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 gráfico de Petersen y el mapa asociado están incrustados en el plano proyectivo . Se identifican los puntos opuestos en el círculo, lo que produce una superficie cerrada de género no orientable 1.

Simetrías

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 este 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]

Caminos y ciclos hamiltonianos

El grafo de Petersen es hipohamiltoniano: al eliminar cualquier vértice, como el vértice central en el dibujo, el grafo restante es hamiltoniano. Este dibujo con simetría de orden 3 es el que dio Kempe (1886).

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 2-conexo, r -regular 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.

Colorante

Una coloración de 4 colores de los bordes del gráfico de Petersen
Una coloración triple de los vértices del gráfico de Petersen

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 gráfico 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 gráficos completos, es el único gráfico de Kneser cuyo número distintivo no es dos. [10]

Otras propiedades

El gráfico de Petersen:

Conjetura de coloración 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]

Gráficos relacionados

La familia Petersen .

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.

Notas

  1. ^ Como se indicó, esto supone que los grafos de Cayley no necesitan ser conexos. Algunas fuentes requieren que los grafos de Cayley sean conexos, lo que hace que el grafo vacío de dos vértices sea el grafo transitivo por vértices no Cayley más pequeño; según la definición dada por estas fuentes, el grafo de Petersen es el grafo transitivo por vértices conexo más pequeño que no es Cayley.
  2. ^ Esto se deduce del hecho de que es un gráfico de Moore, ya que cualquier gráfico de Moore es el gráfico regular más grande posible con su grado y diámetro. [11]
  3. ^ Los grafos cúbicos con 6 y 8 vértices que maximizan el número de árboles de expansión son escaleras de Möbius .

Referencias

  1. ^ Brouwer, Andries E. , El gráfico de Petersen
  2. ^ Petersen, Julius (1898), "Sur le théorème de Tait", L'Intermédiaire des Mathématiciens , 5 : 225–227
  3. ^ Kempe, AB (1886), "Una memoria sobre la teoría de la forma matemática", Philosophical Transactions of the Royal Society of London , 177 : 1–70, doi :10.1098/rstl.1886.0002, S2CID  108716533
  4. ^ Knuth, Donald E., El arte de la programación informática; volumen 4, prefascículo 0A. Un borrador de la sección 7: Introducción a la búsqueda combinatoria
  5. ^ Babai, László (1995), "Grupos de automorfismo, isomorfismo, reconstrucción", en Graham, Ronald L .; Grötschel, Martín ; Lovász, László (eds.), Manual de combinatoria, vol. I, Holanda Septentrional, págs. 1447-1540, Corolario 1.8, archivado desde el original el 11 de junio de 2010.
  6. ^ de Royle, G. "Gráficos cúbicos simétricos (El censo de Foster)". Archivado el 20 de julio de 2008 en Wayback Machine.
  7. ^ Cameron, Peter J. (2004), "Automorfismos de grafos", en Beineke, Lowell W.; Wilson, Robin J. (eds.), Temas de teoría de grafos algebraicos , Enciclopedia de matemáticas y sus aplicaciones, vol. 102, Cambridge University Press, Cambridge, págs. 135-153, doi :10.1017/CBO9780511529993, ISBN 0-521-80197-4, Sr.  2125091; véase en particular la pág. 153
  8. ^ Holton, DA; Sheehan, J. (1993), El gráfico de Petersen , Cambridge University Press , pág. 32, ISBN 0-521-43594-3
  9. ^ Pegg, Ed Jr. (2002), "Reseña del libro: El colosal libro de las matemáticas" (PDF) , Avisos de la American Mathematical Society , 49 (9): 1084–1086, Bibcode :2002ITED...49.1084A, doi :10.1109/TED.2002.1003756
  10. ^ Albertson, Michael O.; Boutin, Debra L. (2007), "Uso de conjuntos determinantes para distinguir grafos de Kneser", Electronic Journal of Combinatorics , 14 (1): R20, doi : 10.37236/938 , MR  2285824.
  11. ^ ab Hoffman, Alan J. ; Singleton, Robert R. (1960), "Gráficos de Moore con diámetro 2 y 3" (PDF) , IBM Journal of Research and Development , 5 (4): 497–504, doi :10.1147/rd.45.0497, MR  0140437.
  12. ^ Alspach, Brian; Zhang, Cun-Quan (1993), "Cubiertas de ciclos de multigrafos cúbicos", Discrete Math. , 111 (1–3): 11–17, doi :10.1016/0012-365X(93)90135-G.
  13. ^ László Lovász, Alexander Schrijver (1998), "Un teorema de Borsuk para enlaces antipodales y una caracterización espectral de gráficos integrables sin enlaces" (PDF) , Actas de la American Mathematical Society , 126 (5): 1275–1285, doi :10.1090/S0002-9939-98-04244-0, S2CID  7790459
  14. ^ Baird, William; Beveridge, Andrew; Bonato, Anthony; Codenotti, Paolo; Maurer, Aaron; McCauley, John; Valeva, Silviya (2014), "Sobre el orden mínimo de los grafos k-cop-win", Contribuciones a las matemáticas discretas , 9 (1): 70–84, arXiv : 1308.2841 , doi : 10.11575/cdm.v9i1.62207 , MR  3265753
  15. ^ Jakobson, Dmitry; Rivin, Igor (1999), Sobre algunos problemas extremos en teoría de grafos , arXiv : math.CO/9907050 , Bibcode :1999math......7050J
  16. ^ Valdés, L. (1991), "Propiedades extremas de árboles generadores en gráficos cúbicos", Congressus Numerantium , 85 : 143-160.
  17. ^ Biggs, Norman (1993), Teoría de grafos algebraicos (2.ª ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
  18. ^ DeVos, Matt; Nešetřil, Jaroslav ; Raspaud, André (2007), "Sobre mapas de aristas cuya inversa preserva flujos o tensiones", Teoría de grafos en París , Trends Math., Basilea: Birkhäuser, pp. 109–138, doi :10.1007/978-3-7643-7400-6_10, ISBN 978-3-7643-7228-6, Sr.  2279171.
  19. ^ Coxeter, HSM (1950), "Configuraciones autoduales y grafos regulares", Boletín de la Sociedad Matemática Americana , 56 (5): 413–455, doi : 10.1090/S0002-9904-1950-09407-5.
  20. ^ Watkins, Mark E. (1969), "Un teorema sobre coloraciones de Tait con una aplicación a los gráficos generalizados de Petersen", Journal of Combinatorial Theory , 6 (2): 152–164, doi : 10.1016/S0021-9800(69)80116-X
  21. ^ Bailey, Rosemary A. (1997), Encuestas en combinatoria , Cambridge University Press, pág. 187, ISBN 978-0-521-59840-8

Lectura adicional

Enlaces externos