Caminos y ciclos de Euler y de Hamilton

Caminos y ciclos de Euler y de Hamilton

Estructuras de Datos

Ana Lilia Vargas Becerra Antonio Israel Noriega Montoya

Euler

Llamamos CAMINO EULERIANO al camino que recorre todas las aristas de un grafo una sola vez, pero que puede pasar por un mismo vértice varias veces. Cuando el camino comienza y termina en el mismo vértice se le denomina CICLO EULERIANO. Si un grafo tiene un camino euleriano, se dice que el grafo es euleriano.

Leonhard Paul Euler, conocido como Leonhard Euler, fue un matemático y físico suizo. Se trata del principal matemático del siglo XVIII y uno de los más grandes y prolíficos de todos los tiempos, muy conocido por el número de Euler, además por sus contribuciones a la teoría de grafos y recorridos.

Existen dos casos de grafos eulerianos, en el primer caso el camino comienza y termina en el mismo vértice formando un Ciclo Euleriano, y en el segundo el camino comienza y termina en distintos vértices formando un Camino Euleriano

Para que se de el primer caso, que es un Ciclo Euleriano, se han de cumplir las siguientes condiciones: -El grafo es conexo. -El grafo es no dirigido. -Todos los vértices son de grado par. -Se comienza y se termina en el mismo vértice.

Para el segundo caso, que es un Camino Euleriano (no cerrado), se deben cumplir las siguientes condiciones: -El grafo es conexo. -El grafo es no dirigido. -Exactamente 2 vértices son de grado impar y todos los demás vértices son de grado par. -Se comienza en uno de los vértices de grado impar y se terminar el camino el otro vértice de grado impar.

HAMILTONIANOS

Un camino hamiltoniano, en el campo matemático de la teoría de grafos, es un camino de un grafo, una sucesión de aristas adyacentes, que visita todos los vértices del grafo una sola vez. Si además el último vértice visitado es adyacente al primero, el camino es un ciclo hamiltoniano.

William Rowan Hamilton fue un matemático, físico, y astrónomo irlandés, que hizo importantes contribuciones al desarrollo de la óptica, la dinámica, y el álgebra. En 1856, Hamilton inventó un juego matemático llamado el “dodecaedro del viajero”. Tal juego consiste en un dodecaedro cada uno de cuyos veinte vértices estaba etiquetado con el nombre de una ciudad de la época. El objetivo del juego era viajar a lo largo de las aristas del dodecaedro, visitando cada ciudad exactamente una vez y volviendo al punto de partida.

Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).

Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.

El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completo.

• No se conocen condiciones necesarias y suficientes para la existencia de circuitos hamiltonianos. • Si se conocen teoremas que dan condiciones suficientes para la existencia de circuitos hamiltonianos. • Hay propiedades para demostrar que un grafo no contiene un circuito hamiltoniano (ej: grafo con vértice de grado 1). • Un circuito hamiltoniano no puede contener un circuito más pequeño dentro de el.

Caminos y ciclos de Euler y de Hamilton

JUGAR

Determinar si es posible un circuito de Hamilton en el siguiente grafo

Salir

¡ENHORABUENA!

¡Gracias por su atencion!

Estructuras de Datos Noriega Montoya Antonio Israel Vargas Becerra Ana Lilia

Bibliografia:

Bibliografia:

• http://libroweb.alfaomega.com.mx/book/685/free/ovas_statics/cap7/Circuitos%20de%20Euler%20y%20de%20Hamilton.%20Arboleda%20Molina,%20Eduardo.pdf
• http://www.unipamplona.edu.co/unipamplona/portalIG/home_23/recursos/general/11072012/grafo3.pdf
• http://caminoseuler.blogspot.com/p/blog-page.html#:~:text=Un%20camino%20de%20Euler%20es,cada%20arista%20exactamente%20una%20vez.&text=Es%20un%20camino%20de%20Euler,cada%20arista%20exactamente%20una%20vez.
• https://compdiscretas.wordpress.com/2012/11/19/tema-3-ciclo-de-euler-y-de-hamilton/
• http://m4tem4ticasdiscret4s.blogspot.com/2016/11/ciclo-de-hamilton.html
• http://caminoseuler.blogspot.com/p/blog-page.html

Inicio