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 útil y contraejemplo para muchos problemas en la 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 sin coloración de tres bordes. [1]
Gráfico de Petersen | |
---|---|
Lleva el nombre de | Julius Petersen |
Vértices | 10 |
Bordes | 15 |
Radio | 2 |
Diámetro | 2 |
Circunferencia | 5 |
Automorfismos | 120 (S 5 ) |
Número cromático | 3 |
Índice cromático | 4 |
Índice cromático fraccional | 3 |
Género | 1 |
Propiedades | Cúbico Snark transitivo a distancia muy regular |
Tabla de gráficos y parámetros |
Aunque el gráfico generalmente se atribuye a Petersen, de hecho apareció 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 bordes 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". [2]
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 curvas tropicales racionales de cinco puntas.
Construcciones
El gráfico de Petersen es el complemento del gráfico lineal de. También es 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 un borde si y solo si los correspondientes subconjuntos de 2 elementos están separados entre sí. Como un gráfico de Kneser de la formaes un ejemplo de un gráfico impar .
Geométricamente, la gráfica de Petersen es la gráfica formada por los vértices y aristas del hemidodecaedro , es decir, un dodecaedro con puntos, líneas y caras opuestas identificadas juntas.
Embeddings
El gráfico de Petersen no es plano . Cualquier grafo no plano tiene como menor el grafo completo , o el gráfico bipartito completo , pero el gráfico de Petersen tiene a ambos como menores. Laminor se puede formar contrayendo los bordes de una combinación perfecta , por ejemplo, los cinco bordes cortos en la primera imagen. La menor puede formarse eliminando un vértice (por ejemplo, el vértice central del dibujo tridimensional) y contrayendo un borde incidente a 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 (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 quita 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 en este dibujo se cruza como máximo una vez, por lo que el gráfico de Petersen es 1-plano . En un toro, el gráfico de Petersen se puede dibujar sin cruces de bordes; por tanto, tiene un género orientable 1.
El gráfico de Petersen también se puede dibujar (con cruces) en el plano de tal manera que todos los bordes 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 de 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 un casquete en cruz dentro de la estrella de cinco puntos en el centro del dibujo y enrutando los bordes de la estrella a través de este casquete en cruz; el dibujo resultante tiene seis caras pentagonales. Esta construcción forma un mapa regular y muestra que el gráfico de Petersen tiene un género 1 no orientable .
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 ruta de tres bordes dirigida en el gráfico de Petersen se puede transformar en cualquier otra ruta de este tipo mediante una simetría del gráfico. [3] Es uno de los 13 gráficos regulares de distancia cúbica . [4]
El grupo de automorfismo del gráfico de Petersen es el grupo simétrico ; la acción deen el gráfico de Petersen se deduce de su construcción como un gráfico de Kneser . Cada homomorfismo del gráfico de Petersen consigo mismo que no identifica vértices adyacentes es un automorfismo. Como se muestra en las figuras, los dibujos del gráfico de Petersen pueden exhibir simetría de cinco o tres direcciones, pero no es posible dibujar el gráfico de Petersen en el plano de tal manera que el dibujo exhiba el grupo de simetría completo del grafico.
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. [5]
Ciclos y caminos hamiltonianos
El gráfico de Petersen tiene una trayectoria hamiltoniana pero no un ciclo hamiltoniano . Es el gráfico cúbico sin puentes 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 conectado 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 pide una trayectoria hamiltoniana y se verifica mediante el gráfico de Petersen.
Solo se conocen cinco gráficos transitivos de vértice 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 de 2 conexiones con un máximo de 3 r + 1 vértices, entonces G es hamiltoniano o G es el gráfico de Petersen. [7]
Para ver que el gráfico de Petersen no tiene un ciclo hamiltoniano C , considere los bordes del corte que desconectan los 5 ciclos internos del externo. Si hay un ciclo hamiltoniano, se debe elegir un número par de estos bordes. Si solo se eligen dos de ellos, sus vértices finales deben ser adyacentes en los dos 5 ciclos, lo que no es posible. De ahí que se elijan 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. Deben elegirse los dos bordes superiores del 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 regulares de diez vértices 3 que tienen un ciclo hamiltoniano y mostrar que ninguno de ellos es el gráfico de Petersen, al encontrar un ciclo en cada uno de ellos que sea más corto que cualquier ciclo en el gráfico 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í, el gráfico tiene un ciclo de 3 o 4 ciclos y, por lo tanto, no puede ser el gráfico de Petersen. Si dos cuerdas conectan los vértices opuestos de C con los vértices a una distancia cuatro a lo largo de C , hay nuevamente un ciclo de 4. El único caso restante 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 de cinco, no se puede formar de esta manera y no tiene un ciclo hamiltoniano.
Colorante
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 un colorante de lista con 3 colores, según el teorema de Brooks para colorantes de lista.
El gráfico de Petersen tiene un índice cromático 4; colorear los bordes requiere cuatro colores. Como gráfico cúbico sin puentes conectado con índice cromático cuatro, el gráfico 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 de snark , un resultado conjeturado por WT Tutte y anunciado en 2001 por Robertson, Sanders, Seymour y Thomas, [8] establece que cada snark tiene el gráfico de Petersen como menor .
Además, el gráfico tiene un índice cromático fraccional 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 conjetura de Goldberg-Seymour de larga data 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 color (posiblemente incorrecto) que rompa todas sus simetrías; es decir, su número distintivo es tres. Excepto por los gráficos completos, es el único gráfico de Kneser cuyo número distintivo no es dos. [9]
Otras propiedades
El gráfico de Petersen:
- está conectado en 3 y, por lo tanto, está conectado en 3 bordes y sin puente. Consulte el glosario .
- tiene la independencia número 4 y es tripartita. Consulte el glosario .
- es cúbico , tiene dominación número 3 y tiene una combinación perfecta y un factor 2 .
- tiene 6 combinaciones perfectas distintas.
- es el gráfico cúbico más pequeño de circunferencia 5. (Es el único- jaula . De hecho, dado que solo tiene 10 vértices, es el único- Gráfico de Moore .) [10]
- es el gráfico cúbico más pequeño con el gráfico de Colin de Verdière invariante μ = 5. [11]
- es la gráfica más pequeña del número de policía 3. [12]
- tiene radio 2 y diámetro 2. Es el gráfico cúbico más grande con diámetro 2. [13]
- tiene espectro de gráfico −2, −2, −2, −2, 1, 1, 1, 1, 1, 3.
- tiene 2000 árboles de expansión , la mayor cantidad de cualquier gráfico cúbico de 10 vértices. [14]
- tiene polinomio cromático . [15]
- tiene polinomio característico , lo que lo convierte en un gráfico integral, un gráfico cuyo espectro consta completamente de números enteros.
Conjetura para colorear de Petersen
Según DeVos, Nesetril y Raspaud, un ciclo de un gráfico G es un conjuntode modo que cada vértice del gráfico ( V ( G ), C ) tiene un grado par. Si son gráficos, definimos un mapa ser ciclo continuo si la imagen previa de cada ciclo de es un ciclo de . Una conjetura fascinante de Jaeger afirma que cada gráfico sin puentes tiene un mapeo de ciclo continuo al gráfico de Petersen. Jaeger mostró que esta conjetura implica la conjetura de 5 ciclos-doble cobertura y la conjetura de Berge-Fulkerson ". [16]
Gráficos relacionados
El gráfico de Petersen generalizado 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 de Schläfli { n / k }. [17] 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 se conectan cada segundo vértice. Los gráficos de Petersen generalizados también incluyen el prisma nel 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 gráficos incrustables sin enlaces , gráficos que se pueden incrustar en un espacio tridimensional de tal manera que no haya dos ciclos en el gráfico vinculados . [18]
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.
Notas
- ^ Brouwer, Andries E. , El gráfico de Petersen
- ^ Knuth, Donald E., El arte de la programación informática; volumen 4, pre-fascículo 0A. Un borrador de la sección 7: Introducción a la búsqueda combinatoria
- ^ Babai, László (1995), "Grupos de automorfismo, isomorfismo, reconstrucción", en Graham, Ronald L .; Grötschel, Martin ; Lovász, László (eds.), Handbook of Combinatorics , I , North-Holland, págs. 1447–1540, Corolario 1.8, archivado desde el original el 11 de junio de 2010.
- ^ Según el censo de Foster .
- ^ Como se indicó, esto supone que los gráficos de Cayley no necesitan estar 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 no Cayley de vértice transitivo más pequeño; Según la definición dada por estas fuentes, el gráfico de Petersen es el gráfico transitivo de vértice conectado más pequeño que no es Cayley.
- ^ Royle, G. "Gráficos simétricos cúbicos (el censo de Foster)". Archivado el 20 de julio de 2008 en la Wayback Machine.
- ^ Holton y Sheehan (1993) , página 32.
- ^ Pegg, Ed, Jr. (2002), "Reseña del libro: The Colossal Book of Mathematics" (PDF) , Notices of the American Mathematical Society , 49 (9): 1084-1086, Bibcode : 2002ITED ... 49.1084A , doi : 10.1109 / TED.2002.1003756
- ^ Albertson, Michael O .; Boutin, Debra L. (2007), "Uso de conjuntos determinantes para distinguir gráficos de Kneser", Electronic Journal of Combinatorics , 14 (1): R20, doi : 10.37236 / 938 , MR 2285824.
- ^ 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.
- ^ László Lovász, Alexander Schrijver (1998). "Un teorema de Borsuk para enlaces antípodas y una caracterización espectral de gráficos incrustables sin enlaces" (PDF) . Actas de la American Mathematical Society . 126 (5): 1275-1285. doi : 10.1090 / S0002-9939-98-04244-0 .
- ^ Baird, William; Beveridge, Andrew; Bonato, Anthony; Codenotti, Paolo; Maurer, Aaron; McCauley, John; Valeva, Silviya (2014), "Sobre el orden mínimo de las gráficas k -cop-win" , Contribuciones a las matemáticas discretas , 9 (1): 70–84, arXiv : 1308.2841 , MR 3265753
- ^ Esto se deriva 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 ( Hoffman y Singleton 1960 ).
- ^ Jakobson y Rivin (1999) ; Valdés (1991) . Los gráficos cúbicos con 6 y 8 vértices que maximizan el número de árboles de expansión son escaleras de Möbius .
- ^ Biggs, Norman (1993), Teoría de grafos algebraicos (2a ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
- ^ DeVos, Matt; Nešetřil, Jaroslav ; Raspaud, André (2007), "Sobre mapas de bordes cuyo inverso preserva flujos o tensiones", Teoría de grafos en París , Trends Math., Basilea: Birkhäuser, págs. 109-138, doi : 10.1007 / 978-3-7643-7400 -6_10 , MR 2279171.
- ^ Coxeter (1950) ; Watkins (1969) .
- ^ Bailey, Rosemary A. (1997), Encuestas sobre combinatoria , Cambridge University Press, pág. 187, ISBN 978-0-521-59840-8
Referencias
- Exoo, Geoffrey; Harary, Frank ; Kabell, Jerald (1981), "Los números de cruce de algunos gráficos de Petersen generalizados", Mathematica Scandinavica , 48 : 184-188, doi : 10.7146 / math.scand.a-11910.
- Coxeter, HSM (1950), "Configuraciones auto-duales y gráficos regulares", Boletín de la American Mathematical Society , 56 (5): 413–455, doi : 10.1090 / S0002-9904-1950-09407-5.
- Holton, DA; Sheehan, J. (1993), The Petersen Graph , Cambridge University Press , doi : 10.2277 / 0521435943 , ISBN 0-521-43594-3.
- Jakobson, Dmitry; Rivin, Igor (1999), Sobre algunos problemas extremos en la teoría de grafos , arXiv : math.CO/9907050
- Kempe, AB (1886), "Memorias sobre la teoría de la forma matemática", Transacciones filosóficas de la Royal Society of London , 177 : 1–70, doi : 10.1098 / rstl.1886.0002
- Lovász, László (1993), Problemas y ejercicios combinatorios (2a ed.), Holanda Septentrional, ISBN 0-444-81504-X.
- Petersen, Julius (1898), "Sur le théorème de Tait", L'Intermédiaire des Mathématiciens , 5 : 225–227
- Schwenk, AJ (1989), "Enumeración de ciclos hamiltonianos en ciertos gráficos de Petersen generalizados", Journal of Combinatorial Theory , Serie B, 47 (1): 53–59, doi : 10.1016 / 0095-8956 (89) 90064-6
- Valdés, L. (1991), "Propiedades extremas de los árboles en expansión en gráficas cúbicas", Congressus Numerantium , 85 : 143-160.
- Watkins, Mark E. (1969), "Un teorema sobre coloraciones de Tait con una aplicación a los gráficos de Petersen generalizados", Journal of Combinatorial Theory , 6 (2): 152-164, doi : 10.1016 / S0021-9800 (69) 80116 -X
enlaces externos
- Weisstein, Eric W. "Petersen Graph" . MathWorld .
- Petersen Graph en la enciclopedia en línea de secuencias de enteros