Gráfico hamiltoniano

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 18 de junio de 2022; la verificación requiere 1 edición .

Un gráfico hamiltoniano  es un gráfico que contiene un ciclo hamiltoniano [1] . En este caso, un ciclo hamiltoniano es un ciclo (camino cerrado) que pasa por cada vértice del gráfico dado exactamente una vez [2] ; es decir, un bucle simple que incluye todos los vértices del gráfico.

También está estrechamente relacionado con un gráfico hamiltoniano el concepto de camino hamiltoniano , que es un camino simple (un camino sin bucles) que pasa por cada vértice del gráfico exactamente una vez [1] . Una ruta hamiltoniana se diferencia de un ciclo en que los puntos inicial y final de una ruta pueden no coincidir, a diferencia de un ciclo. Un ciclo hamiltoniano es un camino hamiltoniano.

El camino, el ciclo y el gráfico hamiltonianos llevan el nombre del matemático irlandés W. Hamilton , quien identificó por primera vez estas clases al investigar el problema de "viajar alrededor del mundo" en un dodecaedro . En este problema, los vértices del dodecaedro simbolizan ciudades famosas como Bruselas , Amsterdam , Edimburgo , Beijing , Praga , Delhi , Frankfurt , etc., y los bordes simbolizan las carreteras que las conectan. El viajero debe dar "la vuelta al mundo", encontrando un camino que pase por todos los vértices exactamente una vez [3] . Para hacer la tarea más interesante, el orden de paso de las ciudades se estableció de antemano. Y para que sea más fácil recordar qué ciudades ya estaban conectadas, se clavó un clavo en cada vértice del dodecaedro, y se marcó el camino pavimentado con una pequeña cuerda que se podía enrollar alrededor del clavo. Sin embargo, esta construcción resultó ser demasiado engorrosa, y Hamilton propuso una nueva versión del juego, reemplazando el dodecaedro con un grafo plano isomorfo al grafo construido en los bordes del dodecaedro [4] .

Condiciones de existencia

Se conoce y se prueba una simple condición necesaria y suficiente para la existencia de un ciclo hamiltoniano [5] .

Una condición necesaria para la existencia de un ciclo hamiltoniano en un grafo no dirigido : si un grafo no dirigido G contiene un ciclo hamiltoniano, entonces no hay vértices en él con grado local . La demostración se sigue de la definición.

Condición elegante: Deje que el gráfico G tenga vértices. Si para cualquier , , el número de vértices con grados menores o iguales a n es menor que n, y para un número impar de vértices con grado no excede , entonces G es un grafo hamiltoniano. Esta condición suficiente no es necesaria [6] .

Como consecuencia del teorema de Posch, obtenemos condiciones suficientes más simples y menos fuertes encontradas por Dirac y Ore.

En 1952, se formuló la condición de Dirac para la existencia de un ciclo hamiltoniano :  sea el número de vértices en un gráfico dado y ; si el grado de cada vértice no es menor que , entonces el gráfico dado es hamiltoniano [7] .

Condición mineral :  sea el número de vértices en el gráfico dado y . Si la desigualdad se cumple para cualquier par de vértices no adyacentes , entonces el gráfico dado es hamiltoniano (en otras palabras: la suma de los grados de dos vértices no adyacentes no es menor que el número total de vértices en el gráfico) [ 7] .

El teorema de Bondi  — Chvatala generaliza las afirmaciones de Dirac y Ore. Un grafo es hamiltoniano si y solo si su cierre es un grafo hamiltoniano. Para un grafo G con n vértices, se construye un cierre añadiendo una arista ( u , v ) a G para cada par de vértices no adyacentes u y v cuya suma de grados sea al menos n [8] .

Un algoritmo para encontrar un camino hamiltoniano

Optimizaciones heurísticas

Con la enumeración directa de variantes de vértices, es posible un aumento significativo en la complejidad promedio de encontrar un camino hamiltoniano en gráficos aleatorios (si se garantiza la existencia de un camino hamiltoniano en el gráfico). Para mejorar este método, es posible verificar en cada paso de la enumeración de alguna parte construida de la cadena si los vértices restantes forman un gráfico conexo (si no lo hacen, entonces la cadena no puede ser el comienzo de una cadena hamiltoniana); en cada paso de la iteración, al elegir el siguiente vértice, pruebe primero los vértices con el grado residual más pequeño (el número de aristas que conducen a los vértices aún no visitados). Además, si este árbol es una cadena, entonces en él es posible un ciclo hamiltoniano. De lo contrario (si el árbol tiene vértices con grado no menor a 3), la construcción de un ciclo hamiltoniano es imposible [9] .

Ejemplos de uso

Criptografía

El ciclo hamiltoniano se utiliza en un sistema de los llamados protocolos de conocimiento cero .

Deje que Peggy y Victor conozcan el mismo gráfico hamiltoniano G, y Peggy conoce el ciclo hamiltoniano en él. Quiere demostrárselo a Víctor sin revelarle el ciclo en sí. Hay un algoritmo de cómo debería actuar [10] :

1. Peggy transforma aleatoriamente el gráfico G. Al mover los puntos y cambiar sus etiquetas, crea un nuevo gráfico H que es topológicamente isomorfo a G. Luego, conociendo el ciclo hamiltoniano en G, puede encontrarlo fácilmente en H. Si no hubiera creado H ella misma, entonces determinar el isomorfismo entre grafos sería una tarea demasiado compleja, cuya solución requiere una enorme cantidad de tiempo. Luego encripta H y obtiene el gráfico H'.

2. Peggy le da a Víctor H'.

3. Víctor le pide a Peggy que:

  1. Demostrar que H' es una copia isomórfica encriptada de G, o
  2. Muestre el ciclo hamiltoniano para H.

4. Peggy cumple con su pedido. ella:

  1. Demuestra que H' es una copia isomórfica encriptada de G, revelando transformaciones y descifrando todo, sin mostrar un ciclo hamiltoniano para G o H, o
  2. Muestra un ciclo hamiltoniano para H, descifrando solo lo que constituye un ciclo hamiltoniano, sin probar que H y G son topológicamente isomorfos.

5. Peggy y Victor repiten los pasos 1-4 n veces.

Si Peggy no está haciendo trampa, podrá decirle a Víctor cualquiera de las pruebas del Paso 3. Sin embargo, si no conoce el ciclo hamiltoniano de G, no podrá crear una H' que satisfaga ambas pruebas. Es cierto que Peggy puede crear un gráfico isomorfo a G o un gráfico con el mismo número de vértices y aristas y un ciclo hamiltoniano adecuado. Y, aunque puede adivinar con un 50 % de probabilidad qué prueba pedirá Víctor en el paso 3, Víctor puede repetir el protocolo suficientes veces hasta que esté seguro de que Peggy conoce el ciclo hamiltoniano en G.

Problemas extremos en teoría de grafos: El problema del viajante de comercio

El viajante de comercio necesita visitar todas las ciudades dentro de un territorio determinado y regresar al punto de partida. Se requiere que el camino sea lo más corto posible. Así, el problema original se transforma en el problema de encontrar la duración mínima (duración o costo) [11] .

El problema se puede reformular en términos de teoría de grafos: construir un grafo G(X, A), cuyos vértices correspondan a ciudades y los bordes correspondan a comunicaciones entre ciudades. La solución de este problema se busca entre los ciclos hamiltonianos del grafo construido.

Hay muchas maneras de resolver este problema. Se pueden distinguir los métodos desarrollados por Bellmore y Nemhauser [12] , Garfinkel y Nemhauser [13] , Held y Karp [14] , Stekhan [15] . También son conocidas las soluciones al problema del viajante de comercio, el método branch andbound y el método de mejora sucesiva de la solución [16] .

Términos relacionados

Un gráfico semi-Hamiltoniano [17] es un gráfico que contiene una cadena simple que pasa por cada uno de sus vértices exactamente una vez. Además, todo gráfico hamiltoniano es semi-hamiltoniano. El ciclo hamiltoniano es un ciclo de expansión simple [18] .

La esencia del problema del ciclo hamiltoniano  es averiguar si un gráfico G dado tiene un ciclo hamiltoniano. Este problema es NP-completo [19] .

La orcadena hamiltoniana de un dígrafo [20]  es un camino simple que pasa por cada vértice del dígrafo exactamente una vez.

Un orciclo hamiltoniano [20] es un orciclo [20] de un dígrafo que pasa por cada uno de sus vértices .

Un dígrafo se denomina semi -hamiltoniano [20] si tiene una orcadena hamiltoniana, y hamiltoniano [20] si tiene un orciclo hamiltoniano.

Véase también

Notas

  1. ↑ 1 2 M. O. Asanov, V. A. Baransky, V. V. Rasin. Matemática discreta: grafos, matroides, algoritmos. - Izhevsk: Regular and Chaotic Dynamics, 2001. - P. 41. - ISBN 5-93972-076-5 .
  2. ↑ Swami, Thulasiraman, 1984 , pág. 55.
  3. ↑ Harari, 2003 , pág. 16-17.
  4. ↑ O. Ore. Gráficos y su aplicación. - Moscú: Mir, 1965. - S. 40-41.
  5. ↑ Dmitri Maksimov. Caminos y rutas  // Ciencia y vida . - 2020. - Nº 2 . - S. 81-86 .
  6. ↑ Harari, 2003 , pág. 86.
  7. ↑ 1 2 Harari, 2003 , pág. 87.
  8. ↑ Swami, Thulasiraman, 1984 , pág. 61.
  9. ↑ Gráficos y algoritmos: Lección 8: Euler y ciclos hamiltonianos . CONOCE Intuir. Consultado el 20 de noviembre de 2014. Archivado desde el original el 29 de noviembre de 2014.
  10. ↑ Schneier, 2002 , pág. 89-90.
  11. ↑ Mainika, 1981 , pág. 241-264.
  12. ↑ Bellmore M., Nemhuser G.L. El problema del viajante de comercio: A. Encuesta. — ORSA vol. 16, 1968. - S. 538-558.
  13. ↑ Garfinkel R., Namhauser GL Programación entera. - Nueva York: John Wiley, Inc., 1972. - S. 354-360.
  14. ↑ Held M., Karp R. El problema del viajante y los árboles de expansión mínimos, Parte II // Matemáticas. Programación. - 1971. - vol. 1.- Pág. 6-25. -doi : 10.1007/ BF01584070 .
  15. ↑ Teorema de Steckhan H.A. sobre problemas simétricos del viajante de comercio. — ORSA, vol. 18, 1970. - S. 1163-1167.
  16. ↑ Mainika, 1981 , pág. 255-264.
  17. ↑ Wilson I.R., Eddiman A.M. Una introducción práctica a Pascal. - Moscú: Radio y comunicación, 1983. - S. 143.
  18. ↑ Tutt, 1988 .
  19. ↑ T. Cormen, C. Leizerson, R. Rivest. Algoritmos. Construcción y análisis. - Moscú: MTSNMO, 2002. - S. 845-846.
  20. ↑ 1 2 3 4 5 Dolgikh, Petrenko, 2007 .

Literatura

Enlaces