Proyecto 5

Caminos de Hamilton

En el campo matemático de la teoría de grafos, un camino hamiltoniano en un grafo es un camino, 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.
El problema de encontrar un ciclo (o camino) hamiltoniano en un grafo arbitrario se sabe que es NP-completo.
Los caminos y ciclos hamiltonianos fueron nombrados después que William Rowan Hamilton, inventor del juego de Hamilton, lanzara un juguete que involucraba encontrar un ciclo hamiltoniano en las aristas de un grafo de un dodecaedro. Hamilton resolvió este problema usando cuaterniones, pero esta solución no se generaliza a todos los grafos.

Un camino hamiltoniano es un camino que visita cada vértice exactamente una vez. Un grafo que contiene un camino hamiltoniano se denomina un ciclo hamiltoniano ó circuito hamiltoniano si es un ciclo que visita cada vértice exactamente una vez (excepto el vértice del que parte y al cual llega). Un grafo que contiene un ciclo hamiltoniano es llamado grafo hamiltoniano.
También se puede decir que los grafos hamiltonianos son cuando cumplen con :
-Circuito hamiltoniano -debe ser conexo -debe ser cerrado.

para resumir:: el camino de hamilton es un camino que recorre todas las aristas solo 1 vez, llegando al mismo punto de partida.

Ejercicio:
hay un problema famoso para este tipo de ejemplos:

en un tablero de ajedrez tratar de hacer el que caballo, recorra todas las casillas del tablero

Ninguno de los dos algoritmos garantiza una solución óptima. Sin embargo, normalmente ambos dan soluciones buenas, próximas a la óptima.

TEOREMA:

Sea K∗n un grafo dirigido completo, es decir K∗n tiene n v´ertices
y para cualquier par de v´ertices distintos x,y al menos la arista (x,y) o (y,x)
est´a en K∗n. Dicho grafo siempre contiene un camino de Hamilton.

DEMOSTRACIÓN:

Sea m≥2 con tm un camino simple que contiene las m−1 aristas: (v1,v2),(v2,v3),...,(vm−1,vm). Si m =n se ha terminado, en otro caso sea v un v´ertice que no aparece en tm.

Si (v,v1) es una arista de K∗n se puede ampliar tm añadiendo esta arista. En
otro caso(v1,v)debe ser una arista. Supongase ahora que(v,v2) esta en el grafo. Entonces se tiene la trayectoria mayor: (v1,v),(v,v2),(v2,v3),...,(vm−1,vm).Si

(v,v2) no es una arista de K∗n entonces (v2,v) debe serlo. Según continua este

proceso hay solo dos posibilidades:

1. para 1 ≤k ≤m−1 las aristas (vk,v),(v,vk+1) están en K∗n y se sustituye (vk,vk+1) por este par de aristas

2. (vm,v) esta en K∗n y se añade esta arista a tm.

En cualquier caso, obtenemos como resultado un camino simple tm+1 que incluye m+1 vértices y tiene m aristas. Este proceso puede repetirse hasta que se tenga un camino de n vértices.

BIBLIOGRAFIA:
http://es.wikipedia.org/wiki/Camino_hamiltoniano
http://docs.google.com/viewer?a=v&q=cache:JNDPlNjUeggJ:www.matap.uma.es/profesor/magalan/MatDis/material/GrafosTema5_1_MatDiscreta.pdf+caminos+de+hamilton&hl=es&gl=mx&pid=bl&srcid=ADGEESjhF5pcBVaMbrj8kWCfuPdH4CVND5lKIyifHirJg6Wi48mGQJPdZAnrvC3y5aU6zwOJstFridndiLhVsNnEZmHNiT4Dq8eyp4XnqA6tEjWcK9wj3hffTsTdMiynAwAKVx1boWKm&sig=AHIEtbTAHM1-WypcKHRi25gFE92alt3ofQ
http://docs.google.com/viewer?a=v&q=cache:7CjbQrO-eUIJ:www.fing.edu.uy/tecnoinf/cursos/mdl2/material/teo/teorico2.pdf+caminos+de+hamilton&hl=es&gl=mx&pid=bl&srcid=ADGEESgw7LRDpcJCpSyzGyrAJuGasfz72trbe0_BF6Og_cA9O-tIqipWnMUho-aEnjfg5C0ev4FPu3B2OvQJ__szzb8icdE-K4e-QOxk-idphdOji1T_hOiEzTHd9USgf8ysHBTyDU7s&sig=AHIEtbRANt1P1qlH2c9kBAV0a2ck182FtA