En la teoría de grafos , una rama de las matemáticas, el teorema de Fleischner da una condición suficiente para que un gráfico contenga un ciclo hamiltoniano . Establece que, si G es un gráfico conectado a 2 vértices , entonces el cuadrado de G es hamiltoniano. lleva el nombre de Herbert Fleischner , quien publicó su prueba en 1974.
Definiciones y declaración
Un gráfico no dirigido G es hamiltoniano si contiene un ciclo que toca cada uno de sus vértices exactamente una vez. Está conectado por 2 vértices si no tiene un vértice de articulación, un vértice cuya eliminación dejaría el gráfico restante desconectado. No todas las gráficas conectadas a dos vértices son hamiltonianas; Los contraejemplos incluyen el gráfico de Petersen y el gráfico bipartito completo K 2,3 .
El cuadrado de G es un gráfico G 2 que tiene el mismo conjunto de vértices como G , y en el que dos vértices son adyacentes si y sólo si tienen la distancia a lo sumo dos en G . El teorema de Fleischner establece que el cuadrado de un grafo finito conectado con dos vértices con al menos tres vértices siempre debe ser hamiltoniano. De manera equivalente, los vértices de cada gráfico 2-vértice-conectado G pueden estar dispuestas en un orden cíclico tal que los vértices adyacentes en este orden están a una distancia como máximo dos entre sí en G .
Extensiones
En el teorema de Fleischner, es posible a la restricción del ciclo de Hamilton en G 2 de modo que para vértices dados v y w de G que incluye dos bordes de G incidente con v y un borde de G incidente con w . Además, si v y w son adyacentes en G , entonces estos son tres bordes diferentes de G . [1]
Además de tener un ciclo hamiltoniano, el cuadrado de un gráfico G conectado con 2 vértices también debe estar conectado al hamiltoniano (lo que significa que tiene una ruta hamiltoniana que comienza y termina en dos vértices designados cualesquiera) y 1-hamiltoniano (lo que significa que, si lo hay, vértice se elimina, el gráfico restante todavía tiene un ciclo hamiltoniano). [2] También debe ser vértice pancíclico , lo que significa que para cada vértice v y cada entero k con 3 ≤ k ≤ | V ( G ) |, existe un ciclo de longitud k que contiene v . [3]
Si una gráfica G no está conectada a 2 vértices, entonces su cuadrado puede tener o no un ciclo hamiltoniano, y determinar si tiene uno es NP-completo . [4]
Un grafo infinito no puede tener un ciclo hamiltoniano, porque cada ciclo es finito, pero Carsten Thomassen demostró que si G es un grafo infinito localmente finito conectado por 2 vértices con un solo extremo, entonces G 2 necesariamente tiene un camino hamiltoniano doblemente infinito. [5] De manera más general, si G es localmente finito, está conectado por 2 vértices y tiene cualquier número de extremos, entonces G 2 tiene un círculo hamiltoniano. En un espacio topológico compacto formado al ver el gráfico como un complejo simplicial y agregar un punto extra en el infinito a cada uno de sus extremos, un círculo hamiltoniano se define como un subespacio que es homeomorfo a un círculo euclidiano y cubre todos los vértices. [6]
Algoritmos
El ciclo hamiltoniano en el cuadrado de un gráfico n- vértice 2 conectado se puede encontrar en tiempo lineal, [7] mejorando con respecto a la primera solución algorítmica de Lau [8] del tiempo de ejecución O (n 2 ) . El teorema de Fleischner se puede utilizar para proporcionar una aproximación 2 al problema del vendedor ambulante de cuello de botella en espacios métricos . [9]
Historia
Una prueba del teorema de Fleischner fue anunciada por Herbert Fleischner en 1971 y publicada por él en 1974, resolviendo una conjetura de Crispin Nash-Williams de 1966 hecha también de forma independiente por LW Beineke y Michael D. Plummer . [10] En su revisión del artículo de Fleischner, Nash-Williams escribió que había resuelto "un problema bien conocido que durante varios años ha derrotado el ingenio de otros teóricos gráficos". [11]
La prueba original de Fleischner era complicada. Václav Chvátal , en el trabajo en el que inventó la tenacidad de los gráficos , observó que el cuadrado de un gráfico conectado con k -vértices es necesariamente k- duro; se conjeturó que los gráficos 2-duras son de Hamilton, de la que otra demostración del teorema de Fleischner habría seguido. [12] Más tarde se descubrieron contraejemplos de esta conjetura, [13] pero la posibilidad de que un límite finito en la tenacidad pueda implicar hamiltonicidad sigue siendo un importante problema abierto en la teoría de grafos. Una demostración más simple tanto del teorema de Fleischner como de sus extensiones por Chartrand et al. (1974) , fue dada por Říha (1991) , [14] y otra demostración simplificada del teorema fue dada por Georgakopoulos (2009a) . [15]
Referencias
Notas
- ^ Fleischner (1976) ; Müttel y Rautenbach (2012) .
- ^ Chartrand y col. (1974) ; Chartrand, Lesniak y Zhang (2010)
- ^ Hobbs (1976) , respondiendo a una conjetura de Bondy (1971) .
- ^ Subterráneo (1978) ; Bondy (1995) .
- ^ Thomassen (1978) .
- ^ Georgakopoulos (2009b) ; Diestel (2012) .
- ↑ Alstrup, Georgakopoulos, Rotenberg, Thomassen (2018)
- ^ Lau (1980) ; Parker y Rardin (1984) .
- ^ Parker y Rardin (1984) ; Hochbaum y Shmoys (1986) .
- ^ Fleischner (1974) . Para las conjeturas anteriores, ver Fleischner y Chartrand, Lesniak & Zhang (2010) .
- ^ Señor 0332573 .
- ^ Chvátal (1973) ; Bondy (1995) .
- ^ Bauer, Broersma y Veldman (2000) .
- ^ Bondy (1995) ; Chartrand, Lesniak y Zhang (2010) .
- ^ Chartrand, Lesniak y Zhang (2010) ; Diestel (2012) .
Fuentes primarias
- Alstrup, Stephen; Georgakopoulos, Agelos; Rotenberg, Eva; Thomassen, Carsten (2018), "A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time", Actas del vigésimo noveno simposio anual ACM-SIAM sobre algoritmos discretos , págs. 1645-1649, doi : 10.1137 / 1.9781611975031.107 , ISBN 978-1-61197-503-1
- Bauer, D .; Broersma, HJ; Veldman, HJ (2000), "No todos los gráficos de 2 difíciles son hamiltonianos" , Actas del quinto taller de Twente sobre gráficos y optimización combinatoria (Enschede, 1997), Matemáticas aplicadas discretas , 99 (1-3): 317-321, doi : 10.1016 / S0166-218X (99) 00141-9 , MR 1743840.
- Bondy, JA (1971), "Gráficos pancíclicos", Actas de la Segunda Conferencia de Luisiana sobre Combinatoria, Teoría de Gráficos y Computación (Universidad Estatal de Luisiana , Baton Rouge, Luisiana , 1971) , Baton Rouge, Luisiana: Universidad Estatal de Luisiana, págs. 167-172, MR 0325458.
- Chartrand, G .; Hobbs, Arthur M .; Jung, HA; Kapoor, SF; Nash-Williams, C. St. JA (1974), "El cuadrado de un bloque está conectado con Hamilton", Journal of Combinatorial Theory , Serie B, 16 (3): 290-292, doi : 10.1016 / 0095-8956 (74 ) 90075-6 , MR 0345865.
- Chvátal, Václav (1973), "Gráficos difíciles y circuitos hamiltonianos", Matemáticas discretas , 5 (3): 215-228, doi : 10.1016 / 0012-365X (73) 90138-6 , MR 0316301.
- Fleischner, Herbert (1974), "El cuadrado de cada gráfico de dos conexiones es hamiltoniano", Journal of Combinatorial Theory , Serie B, 16 : 29–34, doi : 10.1016 / 0095-8956 (74) 90091-4 , MR 0332573.
- Fleischner, H. (1976), "En el cuadrado de los gráficos, la hamiltonicidad y la panciclicidad, la conectividad hamiltoniana y la panconexión son conceptos equivalentes", Monatshefte für Mathematik , 82 (2): 125-149, doi : 10.1007 / BF01305995 , MR 0427135.
- Georgakopoulos, Agelos (2009a), "Una breve demostración del teorema de Fleischner", Matemáticas discretas , 309 (23-24): 6632-6634, doi : 10.1016 / j.disc.2009.06.024 , MR 2558627.
- Georgakopoulos, Agelos (2009b), "Ciclos infinitos de Hamilton en cuadrados de grafos localmente finitos", Advances in Mathematics , 220 (3): 670–705, doi : 10.1016 / j.aim.2008.09.014 , MR 2483226.
- Hobbs, Arthur M. (1976), "El cuadrado de un bloque es el vértice pancíclico", Journal of Combinatorial Theory , Serie B, 20 (1): 1–4, doi : 10.1016 / 0095-8956 (76) 90061-7 , MR 0416980.
- Hochbaum, Dorit S .; Shmoys, David B. (1986), "Un enfoque unificado de algoritmos de aproximación para problemas de cuello de botella" , Journal of the ACM , Nueva York, NY, EE. UU .: ACM, 33 (3): 533–550, doi : 10.1145 / 5925.5933.
- Lau, HT (1980), Encontrar un ciclo hamiltoniano en el cuadrado de un bloque. , Doctor. tesis, Montreal: Universidad McGill. Según lo citado por Hochbaum y Shmoys (1986) .
- Müttel, Janina; Rautenbach, Dieter (2012), "Una breve demostración de la versión versátil del teorema de Fleischner", Matemáticas discretas , 313 (19): 1929-1933, doi : 10.1016 / j.disc.2012.07.032.
- Parker, R. Garey; Rardin, Ronald L. (1984), "Heurística de rendimiento garantizada para el problema del vendedor ambulante de cuello de botella", Operations Research Letters , 2 (6): 269-272, doi : 10.1016 / 0167-6377 (84) 90077-4.
- Říha, Stanislav (1991), "Una nueva demostración del teorema de Fleischner", Journal of Combinatorial Theory , Serie B, 52 (1): 117-123, doi : 10.1016 / 0095-8956 (91) 90098-5 , MR 1109427.
- Thomassen, Carsten (1978), "Caminos hamiltonianos en cuadrados de infinitos bloques localmente finitos", en Bollobás, B. (ed.), Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977) , Annals of Discrete Matemáticas, 3 , Elsevier, págs. 269–277 , doi : 10.1016 / S0167-5060 (08) 70512-0 , ISBN 978-0-7204-0843-0, MR 0499125.
- Underground, Polly (1978), "Sobre gráficas con cuadrados hamiltonianos", Matemáticas discretas , 21 (3): 323, doi : 10.1016 / 0012-365X (78) 90164-4 , MR 0522906.
Fuentes secundarias
- Bondy, JA (1995), "Teoría básica de grafos: caminos y circuitos", Manual de combinatoria, vol. 1, 2 , Amsterdam: Elsevier, págs. 3-110, MR 1373656.
- Chartrand, Gary ; Lesniak, Linda; Zhang, Ping (2010), Graphs & Digraphs (5.a ed.), CRC Press, pág. 139, ISBN 9781439826270.
- Diestel, Reinhard (2012), "10. Ciclos hamiltonianos", Teoría de grafos (PDF) (4ª edición electrónica corregida)