skip to main |
skip to sidebar
Camino que pasa exactamente una vez por cada uno de los vértices del grafo. (Puede no
usar todas las aristas).
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.
Estos conceptos se pueden extender para grafos dirigidos.
Ejemplos
El grafo completo con más de 2 vértices es hamiltoniano.
Todos los grafos ciclos son hamiltonianos.
Todos los sólidos platónicos, considerados como grafos, son hamiltonianos.
Cualquier ciclo hamiltoniano puede ser convertido en un camino hamiltoniano eliminando cualquiera de sus vértices, pero un camino hamiltoniano puede ser extendido en ciclo sólo si los vértices de los extremos son adyacentes.
Teorema de Bondy-Chvátal
La mejor caracterización de los grafos hamiltonianos fue dada en 1972 por el teorema de Bondy-Chvátal que generalizaba los resultados anteriormente encontrados por G. A. Dirac. Básicamente dice que un grafo es hamiltoniano si existen suficientes aristas. Primero debemos definir lo que es la cerradura de un grafo.
Dado un grafo G con n vértices, la cerradura (cl(G)) es construida de manera única a partir de G agregando toda arista u-v si el par no adyacente de vértices u y v cumple que grado(v) + grado(u) ≥ n
Un grafo es hamiltoniano si y sólo si su grafo cerradura es hamiltoniano.
Bondy-Chvátal (1972)
Como todos los grafos completos son hamiltonianos, todos los grafos cuya cerradura sea completa son hamiltonianos. Este resultado se basa en los teoremas de Dirac y Ore.
Un grafo con n vértices (n > 3) es hamiltoniano si cada vértice tiene grado mayor o igual a n/2.
Dirac (1952)
Un grafo con n vértices (n > 3) es hamiltoniano si la suma de los grados de 2 vértices no adyacentes es mayor o igual que n.
Ore (1960)
Sin embargo, existe un resultado anterior a todos estos teoremas.
Un grafo con n vértices (n ≥ 2) es hamiltoniano si la suma de los grados de 2 vértices es mayor o igual que n-1.
L.Redei (1934)
Como puede verse, este teorema pide más hipótesis que los anteriores ya que la propiedad de los grados debe cumplirse para todo vértice en el grafo.
Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.
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-completos.
En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NP-completo son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P.
El tema que escojimos fue el de listas doblemente enlazadas.
Mis compañeras Danya Peralta y Lucero Guzman nos reunimos un par de ocasiones en la FIME para organizarnos y checar mas o menos como hariamos este proyecto e intercambiar nuestras ideas.
Entre las tres llegamos a una conclusion y es asi como hicimos nuestra presentacion.
Yo pienso que debo mejorar un poco en entender las clases, poner mas atencion aunque algunas las vemos algo rapidas y llega un momento en que no entiendo muy claro, es por eso qe acudo a las asesorias.
Nos hemos apoyado mutuamente, ya que si una no entiende algo, pues cualquiera de las otras 2 intregantes nos puede explicar y asi comprender mas el tema.
Se puede decir que las tres hacemos el trabajo por igual, y son muy buenas compañeras, ya que nos repartimos el trabajo de igual manera.
Estos proyectos son buenos hacerlos en equipo para poder apoyarnos entre si, ya que es algo dificil de comprender.
http://daaniiha.blogspot.com/
http://lucygc.blogspot.com/
Introducción
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Pseudocodigo Algoritmo Recursivo
hanoi(n, origen, destino, auxiliar)
si n=1
entonces
mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}
si no
//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino
//{mover n-1 discos de la torre auxiliar a la torre destino}
llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}
fin
fin
Pseudocódigo Algoritmo Iterativo
//los argumentos origen, destino y axuliar son variables representando las tres torres del problema original (pueden ser estructuras o simplemente el nombre de cada torre, en este caso solo representan el nombre de las torres por tanto, se asume que son de tipo texto).
//n es el numero de discos
//pilaN, pilaO, pilaD y pilaA son estructuras de tipo PILA
//tope es una variable de tipo entero.
//varaux es una variable de tipo texto (en este caso por que las torres son representadas unicamente por su nombre, es decir, esta variable debe ser del mismo tipo que origen, destino y auxiliar)
//bandera es una variable de tipo boleano
Solución Iterativa(n, origen, destino, auxiliar)
hacer tope=0 y bandera = falso
repetir mientras (n>0) y (bandera=falso)
repetir mientras (N>1)
//se guardan en las pilas los valores actuales de los parametros
tope=tope+1
pilaN[tope]=n
pilaO[tope]=origen
pilaD[tope]=destio
pilaA[tope]=auxiliar
n=n-1
varaux=destino
destino=auxiliar
auxiliar = varaux
Fin //fin de repetir mientras (N>1)
mover disco de origen a destino
bandera=verdadero
si tope >0 entonces //quiere decir que las pilas no estan vacias
n=pilaN[tope]
origen=pilaO[tope]
destino=pilaD[tope]
auxiliar=pilaA[tope]
tope=tope-1
mover disco de origen a destino
n=n-1
varaux=origen
origen=auxiliar
auxiliar=varaux
bandera=falso
Fin //fin de si tope >0 entonces
Fin //fin de repetir mientras (n>0) y (band=falso)
Fin //fin del metodo
