teorema de fleischner

Teorema sobre gráficos hamiltonianos

Un gráfico de 2 vértices conectados, su cuadrado y un ciclo hamiltoniano en el cuadrado

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 . Afirma que, si es un gráfico conectado con 2 vértices , entonces el cuadrado de es hamiltoniano. Lleva el nombre de Herbert Fleischner , quien publicó su prueba en 1974. ${\displaystyle G}$ ${\displaystyle G}$

Definiciones y declaración

Un grafo no dirigido 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 grafo restante desconectado. No todos los gráficos conectados con 2 vértices son hamiltonianos; los contraejemplos incluyen el gráfico de Petersen y el gráfico bipartito completo . ${\displaystyle G}$ ${\displaystyle K_{2,3}}$

El cuadrado de es un gráfico que tiene el mismo conjunto de vértices que , y en el que dos vértices son adyacentes si y sólo si tienen una distancia como máximo de dos pulgadas . El teorema de Fleischner establece que el cuadrado de un gráfico finito conectado de 2 vértices con al menos tres vértices siempre debe ser hamiltoniano. De manera equivalente, los vértices de cada gráfico conectado con 2 vértices se pueden organizar en un orden cíclico de modo que los vértices adyacentes en este orden estén a una distancia máxima de dos entre sí en . ${\displaystyle G}$ ${\displaystyle G^{2}}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Extensiones

En el teorema de Fleischner, es posible restringir el ciclo hamiltoniano de modo que para los vértices dados y incluya dos aristas de incidente con y una arista de incidente con . Además, si y son adyacentes en , entonces estos son tres bordes diferentes de . ^[1] ${\displaystyle G^{2}}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle G}$

Además de tener un ciclo hamiltoniano, el cuadrado de un gráfico conectado con 2 vértices también debe ser hamiltoniano conexo (lo que significa que tiene un camino hamiltoniano que comienza y termina en dos vértices designados cualesquiera) y 1-Hamiltoniano (lo que significa que si algún vértice se elimina, el gráfico restante todavía tiene un ciclo hamiltoniano). ^[2] También debe ser pancíclico de vértice , lo que significa que para cada vértice y cada número entero con , existe un ciclo de longitud que contiene . ^[3] ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle 3\leq k\leq |V(G)}$ ${\displaystyle k}$ ${\displaystyle v}$

Si un gráfico no está conectado por 2 vértices, entonces su cuadrado puede tener o no un ciclo hamiltoniano, y determinar si lo tiene es NP-completo . ^[4] ${\displaystyle G}$

Un gráfico infinito no puede tener un ciclo hamiltoniano, porque cada ciclo es finito, pero Carsten Thomassen demostró que si es un gráfico infinito localmente finito conectado con 2 vértices y un solo extremo , entonces necesariamente tiene un camino hamiltoniano doblemente infinito. ^[5] De manera más general, si es localmente finito, está conectado por 2 vértices y tiene cualquier número de extremos, entonces 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 adicional 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] ${\displaystyle G}$ ${\displaystyle G^{2}}$ ${\displaystyle G}$ ${\displaystyle G^{2}}$

Algoritmos

El ciclo hamiltoniano en el cuadrado de un gráfico conectado con 2 vértices se puede encontrar en tiempo lineal, ^[7] mejorando la primera solución algorítmica de Lau ^[8] de tiempo de ejecución . El teorema de Fleischner se puede utilizar para proporcionar una aproximación 2 al problema del cuello de botella del viajante en espacios métricos . ^[9] ${\displaystyle n}$ ${\displaystyle O(n^{2})}$

Historia

Herbert Fleischner anunció una prueba del teorema de Fleischner en 1971 y la publicó en 1974, resolviendo una conjetura de 1966 de Crispin Nash-Williams también realizada de forma independiente por LW Beineke y Michael D. Plummer . ^[10] En su reseña 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 de grafos". ^[11]

La prueba original de Fleischner era complicada. Václav Chvátal , en el trabajo en el que inventó la dureza del grafo , observó que el cuadrado de un grafo conectado por vértices es necesariamente tenaz; conjeturó que las gráficas de 2 difíciles son hamiltonianas, de lo que se habría seguido otra prueba del teorema de Fleischner . ^[12] Posteriormente se descubrieron contraejemplos de esta conjetura, ^[13] pero la posibilidad de que un límite finito de tenacidad pueda implicar hamiltonicidad sigue siendo un importante problema abierto en la teoría de grafos. Una prueba más sencilla tanto del teorema de Fleischner como de sus extensiones por Chartrand et al. (1974), fue dada por Říha (1991), ^[14] y Georgakopoulos (2009a) dio otra demostración simplificada del teorema. ^[15] ${\displaystyle k}$ ${\displaystyle k}$

Referencias

Notas

1. Fleischner (1976); Müttel y Rautenbach (2012).
2. Chartrand y col. (1974); Chartrand, Lesniak y Zhang (2010)
3. Hobbs (1976), respondiendo a una conjetura de Bondy (1971).
4. Subterráneo (1978); Bondy (1995).
5. Thomassen (1978).
6. Georgakopoulos (2009b); Diéstel (2012).
7. Alstrup y col. (2018)
8. Lau (1980); Parker y Rardin (1984).
9. Parker y Rardin (1984); Hochbaum y Shmoys (1986).
10. Fleischner (1974). Para las conjeturas anteriores, véase Fleischner y Chartrand, Lesniak y Zhang (2010).
11. SEÑOR 0332573.
12. Chvátal (1973); Bondy (1995).
13. Bauer, Broersma y Veldman (2000).
14. Bondy (1995); Chartrand, Lesniak y Zhang (2010).
15. Chartrand, Lesniak y Zhang (2010); Diéstel (2012).

Fuentes primarias

• Alstrup, Stephen; Georgakopoulos, Agelos; Rothenberg, Eva; Thomassen, Carsten (2018), "Un ciclo hamiltoniano en el cuadrado de un gráfico biconexo en tiempo lineal", 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 , SEÑOR  1743840.
• Bondy, JA (1971), "Gráficos pancíclicos", Actas de la Segunda Conferencia de Luisiana sobre Combinatoria, Teoría de Grafos y Computación (Universidad Estatal de Luisiana, Baton Rouge, Luisiana, 1971) , Baton Rouge, Luisiana: Universidad Estatal de Luisiana, págs. 167–172, SEÑOR  0325458.
• Chartrand, G .; Hobbs, Arthur M .; Jung, HA; Kapoor, SF; Nash-Williams, C. St. JA (1974), "El cuadrado de un bloque está conexo hamiltoniano", Journal of Combinatorial Theory , Serie B, 16 (3): 290–292, doi : 10.1016/0095-8956(74 )90075-6 , SEÑOR  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 , SEÑOR  0316301.
• Fleischner, Herbert (1974), "El cuadrado de todo gráfico biconexo 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, hamiltonicidad y panciclicidad, conectividad hamiltoniana y panconectividad son conceptos equivalentes", Monatshefte für Mathematik , 82 (2): 125–149, doi :10.1007/BF01305995, MR  0427135.
• Georgakopoulos, Agelos (2009a), "Una breve prueba del teorema de Fleischner", Matemáticas discretas , 309 (23–24): 6632–6634, doi : 10.1016/j.disc.2009.06.024 , SEÑOR  2558627.
• Georgakopoulos, Agelos (2009b), "Ciclos infinitos de Hamilton en cuadrados de gráficos localmente finitos", Avances en Matemáticas , 220 (3): 670–705, doi : 10.1016/j.aim.2008.09.014 , SEÑOR  2483226.
• Hobbs, Arthur M. (1976), "El cuadrado de un bloque es pancíclico de vértice", Journal of Combinatorial Theory , Serie B, 20 (1): 1–4, doi : 10.1016/0095-8956(76)90061-7 , señor  0416980.
• Hochbaum, Dorit S .; Shmoys, David B. (1986), "Un enfoque unificado para algoritmos de aproximación para problemas de cuellos 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 prueba 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ísticas de rendimiento garantizadas para el problema del cuello de botella del viajante", Operations Research Letters , 2 (6): 269–272, doi :10.1016/0167-6377(84)90077-4.
• Říha, Stanislav (1991), "Una nueva prueba del teorema de Fleischner", Journal of Combinatorial Theory , Serie B, 52 (1): 117–123, doi : 10.1016/0095-8956(91)90098-5 , SEÑOR  1109427.
• Thomassen, Carsten (1978), "Hamiltonian paths in squares of infinitos localmente finitos", en Bollobás, B. (ed.), Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Matemáticas, vol. 3, Elsevier, págs. 269–277, doi :10.1016/S0167-5060(08)70512-0, ISBN 978-0-7204-0843-0, señor  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 , Ámsterdam: Elsevier, págs. 3–110, SEÑOR  1373656.
• Chartrand, Gary ; Lesniak, Linda; Zhang, Ping (2010), Gráficos y dígrafos (5ª ed.), CRC Press, p. 139, ISBN 9781439826270.
• Diestel, Reinhard (2012), "10. Ciclos hamiltonianos", Teoría de grafos (PDF) (cuarta edición electrónica corregida)