6.11 Caminos hamiltonianos. Viaje a Vietnam.

Aplicaciones de la Teoría de Grafos a la vida real

Alberto Conejero y Cristina JordánDepto. Matemática Aplicada E.T.S. Ingeniería InformáticaUniversitat Politècnica de València

Nuestra agencia de viajes “Hamiltonianos & Cia.” ha recibido el encargo de organizar unviaje de dos semanas visitando los lugares más emblemáticos de Vietnam y Camboya.¿Sería posible diseñar el recorrido para nuestros clientes sin repetir ciudades?

Siem Reap

Aplicaciones de la Teoría de Grafos a la vida real

Nuestro problema

6.11 Caminos hamiltonianos. Viaje a VietnamImágenes de Maps.com

Aplicaciones de la Teoría de Grafos a la vida real

Siem Reap

Modelizamos con un grafo G=(V,E) los vuelos disponibles entre las ciudades que nos interesa visitar

Nuestro problema

V={ciudades a visitar}E={(u,v) / u,v œ V y hay vuelos entre

las ciudades u y v}G es grafo no dirigido

Objetivo: Encontrar un camino hamiltoniano

6.11 Caminos hamiltonianos. Viaje a Vietnam

Aplicaciones de la Teoría de Grafos a la vida real

¿Sabemos cuándo un grafo es hamiltoniano?

¿Sabemos cuándo un grafo tiene camino hamiltoniano?

Se conocen condiciones necesarias y condiciones suficientesNo se conoce ninguna condición necesaria y suficiente

Se conoce alguna condición suficiente (por ejemplo, la condición de Dirac)No se conoce ninguna condición necesaria y suficiente

Recordemos

Transformar el problema en uno de ciclo hamiltonianoIdea

6.11 Caminos hamiltonianos. Viaje a Vietnam

Caracterización de camino hamiltoniano

Aplicaciones de la Teoría de Grafos a la vida real

Sea G=(V,E) grafo no dirigido, |V|=n

Existe camino hamiltoniano en G

si y sólo si

G’ =(V’,E’) es hamiltoniano

donde V’=V » {a} y E’= E » {(u,a) / u œ V}

6.11 Caminos hamiltonianos. Viaje a Vietnam

Aplicaciones de la Teoría de Grafos a la vida real

Existe ciclo hamiltoniano en G'

G

G’

Existe camino hamiltoniano en G

( )

?

¿Camino ham. ?

¿Ciclo ham.?

Caracterización de camino hamiltoniano

V’=V»{a} y E’= E»{(u,a) / uœV}

6.11 Caminos hamiltonianos. Viaje a Vietnam

Aplicaciones de la Teoría de Grafos a la vida real

Existe ciclo hamiltoniano en G'

G

G’

(

Existe camino hamiltoniano en G

)

?

¿Camino ham. ?

¿Ciclo ham.?

Caracterización de camino hamiltoniano

V’=V»{a} y E’= E»{(u,a) / uœV}

6.11 Caminos hamiltonianos. Viaje a Vietnam

Extensión de la caracterización

Extremo- inicial: cualquiera- final: cualquiera

Extremo- inicial: conocido - final: conocido

Extremo- inicial: en un conjunto- final: conocido

Extremo- inicial: en un conjunto- final: en un conjunto

6.11 Caminos hamiltonianos. Viaje a Vietnam

Nuestra agencia de viajes “Hamiltonianos & Cia.” ha recibido el encargo de organizar un viaje de dos semanas visitando los lugares más emblemáticos de Vietnam y Camboya. ¿Sería posible diseñar el recorrido para nuestros clientes sin repetir ciudades?

Aplicaciones de la Teoría de Grafos a la vida real

Hamiltonianos & Cia.

Ficticio

Hanoi

Siem Reap

Ho Chi Min

Vinh

Nha Trang

Danang

6.11 Caminos hamiltonianos. Viaje a Vietnam

Hamiltonianos & Cia.

Aplicaciones de la Teoría de Grafos a la vida real

Ficticio

Hanoi

Siem Reap

Ho Chi Min

Vinh

Nha Trang

Danang

Ficticio, Hanoi, Vinh, Nha Trang, Da Nang, Ho Chi Min,Siem Reap,Ficticio

Teorema d’Ore Ciclo hamiltoniano

6.11 Caminos hamiltonianos. Viaje a Vietnam

Hamiltonianos & Cia.

Aplicaciones de la Teoría de Grafos a la vida real

Hanoi

Siem Reap

Ho Chi Min

Vinh

Nha Trang

Danang

Ficticio, Hanoi, Vinh, Nha Trang, Da Nang, Ho Chi Min,Siem Reap,Ficticio

Ciclo hamiltoniano

Camino

6.11 Caminos hamiltonianos. Viaje a Vietnam

Aplicaciones de la Teoría de Grafos a la vida real

Modelización¿Hay un camino hamiltonianoque empiece en Hanoiy termine en Ho Chi Min?

Nuestros clientes quieren visitar mercados populares de Hanoi y Ho Chi Min, y nos preguntan si podríamos arreglar el recorrido para que esas dos ciudades sean respectivamente comienzo y fin del viaje.

Hamiltonianos & Cia.

Hanoi

Siem Reap

Ho Chi Min

Vinh

Nha Trang

Danang

6.11 Caminos hamiltonianos. Viaje a Vietnam

Aplicaciones de la Teoría de Grafos a la vida real

Hamiltonianos & Cia.

Ficticio

Hanoi

Siem Reap

Ho Chi Min

Vinh

Nha Trang

Danang

Método “grado 2” No existe ciclo hamiltoniano

6.11 Caminos hamiltonianos. Viaje a Vietnam

Aplicaciones de la Teoría de Grafos a la vida real

G

Método vértices de grado 2

No existe ciclo hamiltoniano en G’

No existe camino hamiltoniano en GNo es posible contentar a nuestros clientes

Modelización¿Hay camino hamiltoniano que empiece en Hanoi y termine en Ho Chi Min?

Nuestros clientes quieren visitar mercados populares de Hanoi y Ho Chi Min, y nos preguntan si podríamos arreglar el recorrido para que esas dos ciudades sean respectivamente comienzo y fin del viaje.

Hanoi Ho Chi Min

Hamiltonianos & Cia.

6.11 Caminos hamiltonianos. Viaje a Vietnam