Hispanopedia Wiki
Articulo de referencia

descomposición hamiltoniana

Descomposición hamiltoniana de Walecki del grafo completo K 9 {\displaystyle K_{9}} En la teoría de grafos , una rama de las matemáticas, una descomposición hamiltoniana de un g...

Hispanopedia WikiContenido en espanolLectura gratuita
Descomposición hamiltoniana de Walecki del grafo completoK9{\displaystyle K_{9}}

En la teoría de grafos , una rama de las matemáticas, una descomposición hamiltoniana de un grafo dado es una partición de las aristas del grafo en ciclos hamiltonianos . Las descomposiciones hamiltonianas se han estudiado tanto para grafos no dirigidos como para grafos dirigidos . En el caso de los grafos no dirigidos, una descomposición hamiltoniana también puede describirse como una 2-factorización del grafo, de modo que cada factor sea conexo.

Condiciones necesarias

Para que exista una descomposición hamiltoniana en un grafo no dirigido, este debe ser conexo y regular , de grado par . Un grafo dirigido con dicha descomposición debe ser fuertemente conexo y todos sus vértices deben tener el mismo grado de entrada y de salida, pero este grado no tiene por qué ser par. [ 1 ]

Clases especiales de grafos

Gráficos completos

Cada gráfico completo con un número imparnorte{\displaystyle n}de vértices tiene una descomposición hamiltoniana. Este resultado, que es un caso especial del problema de Oberwolfach de descomponer grafos completos en 2-factores isomorfos, fue atribuido a Walecki por Édouard Lucas en 1892. La formulación original del problema de Oberwolfach pregunta cómo hacer un plano de asientos paranorte{\displaystyle n}personas mayores(norte−1)/2{\displaystyle (n-1)/2}cenas en un conjunto dado de mesas circulares de diferentes tamaños, de manera que cada participante se siente junto a otro exactamente una vez. El teorema de Walecki corresponde al caso en que hay una sola mesa.

Lugares de construcción originales de Waleckinorte−1{\displaystyle n-1}de los vértices en un polígono regular y cubre el grafo completo en este subconjunto de vértices con(norte−1)/2{\displaystyle (n-1)/2}Caminos hamiltonianos que zigzaguean a través del polígono, con cada camino rotado con respecto a los demás por un múltiplo deπ/(norte−1){\displaystyle \pi /(n-1)}. Los caminos pueden entonces completarse en ciclos hamiltonianos conectando sus extremos a través del vértice restante. [ 2 ]

Expandir un vértice de un2k{\displaystyle 2k}-gráfico regular en una camarilla de2k{\displaystyle 2k}Los vértices, uno por cada extremo de una arista en el vértice reemplazado, no pueden cambiar si el grafo tiene una descomposición hamiltoniana. El proceso inverso de expansión, al colapsar una camarilla a un solo vértice, transformará cualquier descomposición hamiltoniana en el grafo más grande en una descomposición hamiltoniana en el grafo original. A la inversa, la construcción de Walecki se puede aplicar a la camarilla para expandir cualquier descomposición hamiltoniana del grafo más pequeño en una descomposición hamiltoniana del grafo expandido. [ 3 ]

Un tipo de análogo de un grafo completo, en el caso de grafos dirigidos, es un torneo . Este es un grafo en el que cada par de vértices distintos está conectado por una única arista dirigida, de uno al otro; por ejemplo, dicho grafo puede describir el resultado de un torneo de todos contra todos en deportes, donde cada competidor en el torneo juega contra todos los demás competidores, y las aristas están dirigidas desde el perdedor de cada juego hasta el ganador. Respondiendo a una conjetura de Paul Kelly de 1968, [ 4 ] Daniela Kühn y Deryk Osthus demostraron en 2012 que todo torneo regular suficientemente grande tiene una descomposición hamiltoniana. [ 5 ]

Grafos planares

El grafo medial del grafo de Herschel es un grafo planar 4-regular sin descomposición hamiltoniana. Las regiones sombreadas corresponden a los vértices del grafo de Herschel subyacente.

Para grafos planares 4-regulares , se pueden derivar condiciones necesarias adicionales del teorema de Grinberg . Un ejemplo de un grafo planar 4-regular que no cumple estas condiciones y no tiene una descomposición hamiltoniana es el grafo medial del grafo de Herschel . [ 6 ]

Prismas

Problema sin resolver en matemáticas
¿Cada prisma sobre un grafo 3-conexo y 3-regular tiene una descomposición hamiltoniana?
Más problemas sin resolver en matemáticas

El prisma sobre un grafo es su producto cartesiano con el grafo completo de dos vértices. Por ejemplo, el prisma sobre un grafo cíclico es el grafo de un prisma geométrico . Los grafos 4-regulares obtenidos como prismas sobre grafos 3-regulares se han estudiado particularmente con respecto a la descomposición hamiltoniana. Cuando el grafo 3-regular subyacente es 3-conexo por vértices , el prisma 4-regular resultante siempre tiene un ciclo hamiltoniano y, en todos los ejemplos que se han probado, una descomposición hamiltoniana. Basándose en esta observación, Alspach y Rosenfeld conjeturaron en 1986 que todos los prismas sobre grafos 3-regulares 3-conexos por vértices tienen una descomposición hamiltoniana. [ 7 ] [ 8 ]

Se sabe que muchas clases de grafos 3-regulares con 3 vértices conexos poseen prismas con descomposiciones hamiltonianas. En particular, esto ocurre cuando el grafo 3-regular es planar y bipartito, cuando es un grafo de Halin , cuando es en sí mismo un prisma o una escalera de Möbius , o cuando es un grafo de Petersen generalizado de orden divisible por cuatro. [ 8 ] [ 9 ]

Gráficos simétricos

Existen infinitos grafos transitivos de vértices (grafos en los que cada vértice es simétrico a todos los demás) que no tienen descomposición hamiltoniana. En particular, esto se aplica a los grafos de Cayley cuyos vértices describen los elementos de un grupo y cuyos elementos describen la multiplicación por generadores del grupo . Infinitos grafos de Cayley 6-regulares no tienen descomposición hamiltoniana, y existen grafos de Cayley de grado par arbitrariamente grande sin descomposición hamiltoniana. Una forma de construir estos grafos es mediante expansiones repetidas por cliques, que preservan la simetría y no pueden cambiar la existencia de una descomposición hamiltoniana. [ 3 ]

Hipergrafos uniformes

Los problemas de descomposición para hipergrafos son, en general, mucho más difíciles que para grafos. A diferencia de los grafos, los hipergrafos admiten múltiples nociones no equivalentes de ciclos (véase Ciclos de hipergrafos ).

La más simple de estas nociones es el ciclo de Berge . En 2014, Kühn y Osthus [ 10 ] demostraron que el ciclo completok{\displaystyle k}Hipergrafo uniformeKnorte(k){\displaystyle K_{n}^{(k)}}admite una descomposición en ciclos de Hamilton-Berge siempre quenorte{\displaystyle n}divide(nortek){\displaystyle {\tbinom {n}{k}}}.

Problema sin resolver en matemáticas
Para números enterosnorte{\displaystyle n}yk{\displaystyle k}dóndenorte{\displaystyle n}divide(nortek){\displaystyle {\tbinom {n}{k}}}¿lo hace el completo?k{\displaystyle k}Hipergrafo uniformeKnorte(k){\displaystyle K_{n}^{(k)}}¿Admite una descomposición hamiltoniana estricta?
Más problemas sin resolver en matemáticas

Sin embargo, para la noción de ciclo más comúnmente utilizada en hipergrafos —el ciclo ajustado— sigue siendo un problema abierto si el ciclo completok{\displaystyle k}Hipergrafo uniformeKnorte(k){\displaystyle K_{n}^{(k)}}admite una descomposición hamiltoniana. [ 11 ] Formulada como el problema de la disposición de asientos del problema de Oberwolfach presentado anteriormente, encontrar estas descomposiciones corresponde al caso en el que cada conjunto dek{\displaystyle k}Las personas se sientan consecutivamente exactamente una vez. En este caso, el número de cenas tiene que ser(norte−1k−1)/k{\displaystyle {\tbinom {n-1}{k-1}}/k}.

El teorema de Baranyai aborda un problema similar, al encontrar una descomposición de la ecuación completa.k{\displaystyle k}-Hipergrafo uniforme en emparejamientos perfectos.

Número de descomposiciones

Todo grafo no dirigido 4-regular tiene un número par de descomposiciones hamiltonianas. Más concretamente, por cada dos aristasmi{\displaystyle e}yF{\displaystyle f}de un grafo 4-regular, el número de descomposiciones hamiltonianas en las quemi{\displaystyle e}yF{\displaystyle f}pertenecer al mismo ciclo es par. Si un2k{\displaystyle 2k}-un grafo regular tiene una descomposición hamiltoniana, tiene al menos un triple factorial número de descomposiciones,

(3k−2)⋅(3k−5)⋯7⋅4⋅1.{\displaystyle (3k-2)\cdot (3k-5)\cdots 7\cdot 4\cdot 1.}

Por ejemplo, los grafos 4-regulares que tienen una descomposición hamiltoniana tienen al menos cuatro de ellas; los grafos 6-regulares que tienen una descomposición hamiltoniana tienen al menos 28, etc. De ello se deduce que los únicos grafos cuyas descomposiciones hamiltonianas son únicas son los grafos cíclicos . [ 12 ]

Complejidad computacional

Probar si un grafo arbitrario tiene una descomposición hamiltoniana es NP-completo , tanto en el caso dirigido como en el no dirigido. [ 13 ] En particular, la pregunta es NP-completa para grafos regulares de un grado par especificado; por ejemplo, para grafos 4-regulares.

Los grafos de líneas de grafos cúbicos son 4-regulares y tienen una descomposición hamiltoniana si y solo si el grafo cúbico subyacente tiene un ciclo hamiltoniano. [ 14 ] [ 15 ] Como consecuencia, la descomposición hamiltoniana sigue siendo NP-completa para clases de grafos que incluyen grafos de líneas de instancias difíciles del problema del ciclo hamiltoniano . Por ejemplo, la descomposición hamiltoniana es NP-completa para los grafos planares 4-regulares, porque incluyen los grafos de líneas de grafos planares cúbicos. Por otro lado, esta equivalencia también implica que la descomposición hamiltoniana es fácil para los grafos de líneas 4-regulares cuando sus grafos cúbicos subyacentes tienen problemas de ciclo hamiltoniano fáciles.

Los grafos regulares aleatorios de grado par casi con seguridad tienen una descomposición hamiltoniana, y más aún, existe un algoritmo aleatorio de tiempo polinomial que, al recibir como entrada un grafo regular aleatorio de grado par, casi con seguridad encuentra una descomposición hamiltoniana en él. [ 16 ]

Véase también

  • Arboricidad lineal , un tipo diferente de partición restringida en subgrafos de grado máximo dos.

Referencias

  1. ↑ Bermond, J.-C. (1978), "Descomposiciones hamiltonianas de grafos, grafos dirigidos e hipergrafos" , en Bollabás, B. (ed.), Avances en la teoría de grafos , Annals of Discrete Mathematics, vol.  3, pp. 21–28 , doi : 10.1016/S0167-5060(08)70494-1 , ISBN  9780720408430, MR 0505807 
  2. ↑ Alspach, Brian (2008), "La maravillosa construcción de Walecki", Boletín del Instituto de Combinatoria y sus Aplicaciones , 52 : 7–20 , MR 2394738 
  3. 1 2 Bryant, Darryn; Dean, Matthew (2015), "Grafos transitivos por vértices que no tienen descomposición hamiltoniana", Journal of Combinatorial Theory , Serie B, 114 : 237–246 , arXiv : 1408.5211 , doi : 10.1016/j.jctb.2015.05.007 , MR 3354297 
  4. ↑ Moon, John W. (1968), Temas sobre torneos , Nueva York, Montreal, Londres: Holt, Rinehart and Winston, Ejercicio 9, página 9, MR 0256919 
  5. ↑ Kühn, Daniela ; Osthus, Deryk (2013), "Descomposiciones de Hamilton de expansores regulares: una demostración de la conjetura de Kelly para torneos grandes", Advances in Mathematics , 237 : 62–146 , arXiv : 1202.6219 , doi : 10.1016/j.aim.2013.01.005 , MR 3028574 
  6. ^ Bondy, JA ; Häggkvist, R. (1981), "Ciclos de Hamilton con bordes disjuntos en gráficos planos regulares de 4", Aequationes Mathematicae , 22 (1): 42– 45, doi : 10.1007/BF02190157 , MR 0623315 
  7. ↑ Alspach, Brian ; Rosenfeld, Moshe (1986), "Sobre descomposiciones hamiltonianas de prismas sobre 3-politopos simples", Graphs and Combinatorics , 2 (1): 1–8 , doi : 10.1007/BF01788070 , MR 1117125 
  8. 1 2 Rosenfeld, Moshe; Xiang, Ziqing (2014), "Descomposición hamiltoniana de prismas sobre grafos cúbicos", Matemáticas Discretas y Ciencias de la Computación Teórica , 16 (2): 111– 124, doi : 10.46298/dmtcs.2079 , MR 3349112 
  9. ↑ Čada, romano; Káiser, Toma; Rosenfeld, Moshé; Ryjáček, Zdeněk (2004), "Descomposiciones hamiltonianas de prismas sobre gráficos cúbicos", Matemáticas discretas , 286 ( 1– 2): 45– 56, doi : 10.1016/j.disc.2003.11.044 , SEÑOR 2084278 
  10. ↑ Kühn, D. ; Osthus, D. (2014). "Descomposiciones de hipergrafos uniformes completos en ciclos de Hamilton Berge" . Journal of Combinatorial Theory, Series A. 126 : 128–135 . arXiv : 1403.7932 . doi : 10.1016 /j.jcta.2014.04.010 .
  11. ↑ Bailey, R.; Stevens, B. (2010). "Descomposiciones hamiltonianas de hipergrafos k-uniformes completos" . Matemáticas Discretas . 310 (22): 3088– 3095. doi : 10.1016/j.disc.2009.03.047 .
  12. ↑ Thomason, AG (1978), "Ciclos hamiltonianos y grafos con coloración de aristas única", Avances en teoría de grafos (Conferencia Combinatoria de Cambridge, Trinity College, Cambridge, 1977) , Anales de Matemáticas Discretas, vol. 3, págs. 259–268 , MR 0499124   
  13. ↑ Péroche, B. (1984), "NP-completitud de algunos problemas de partición y cobertura en grafos", Matemáticas Aplicadas Discretas , 8 (2): 195– 208, doi : 10.1016/0166-218X(84)90101-X , MR 0743024 
  14. ^ Kotzig, Anton (1957), "Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades", Časopis Pro Pěstování Matematiky , 82 : 76– 92, doi : 10.21136/CPM.1957.117236 , SEÑOR 0090815 
  15. ^ Martin, Pierre (1976), "Cycles hamiltoniens dans les graphes 4-réguliers 4-connexes", Aequationes Mathematicae , 14 (1/2): 37– 40, doi : 10.1007/BF01836203 , SEÑOR 0414442 
  16. ↑ Kim, Jeong Han ; Wormald, Nicholas C. (2001), "Emparejamientos aleatorios que inducen ciclos hamiltonianos y descomposiciones hamiltonianas de grafos regulares aleatorios", Journal of Combinatorial Theory , Serie B, 81 (1): 20–44 , doi : 10.1006/jctb.2000.1991 , MR 1809424