lunes, 31 de mayo de 2010

PUNTOS EXTRAS

CICLO DE EULER


Un ciclo euleriano es aquel camino que recorre todos los vértices (nodos) de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde coinciden vértice inicial o de salida y vértice final o meta). Una definición más formal lo define como: "aquel ciclo que contiene todas las aristas de un grafo solamente una vez".




En la imagen, c= {1,2,3,4,6,3,5,4,1} es un ciclo euleriano, luego es un grafo euleriano.

Un grafo es una representación, un modelo, compuesto por un número determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría de grafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoniano es un camino que recorre todos los vértices de un grafo sin pasar dos veces por el mismo vértice. Si el camino es cerrado se dice un ciclo hamiltoniano.

Si un grafo admite un ciclo euleriano, se denomina grafo euleriano.

Determina el ciclo de Euler en la siguiente figura:

¿Para que es útil?

en la vida diaria lo usamos muy frecuentemente, cuando queremos visitar todos nuestros amigos y al final volver a la casa, o cuando estamos en un museo, queremos recorrer todas las salas y volver a salir por la misma entrada. es mas que nada para analizar todo el camino, y ver si hay algun error y mejorarlo.


PUNTOS EXTRAS

ALGORITMO DE DIJKSTRA

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo dirigido y con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.



















ALGORITMO

Teniendo un grafo dirigido ponderado de N nodos no aislados, sea x el nodo inicial, un vector D de tamaño N guardará al final del algoritmo las distancias desde x al resto de los nodos.

1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0.
2. Sea a = x (tomamos a como nodo actual).
3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi.
4. Si la distancia desde x hasta vi guardada en D es mayor que la distancia desde x hasta a sumada a la distancia desde a hasta vi; esta se sustituye con la segunda nombrada, esto es:
si (Di > Da + d(a, vi)) entonces Di = Da + d(a, vi)
5. Marcamos como completo el nodo a.
6. Tomamos como próximo nodo actual el de menor valor en D (puede hacerse almacenando los valores en una cola de prioridad) y volvemos al paso 3 mientras existan nodos no marcados.
Una vez terminado al algoritmo, D estará completamente lleno.



¿ Para que es útil?

Muchas veces en la vida diaria queremos encontrar el camino mas eficiente para llegar a nuestro destino, este algoritmo es perfecto, ya que, evalúa todas las posibles rutas y escoje las mas corta para llegar al destino. Ciendo así la ruta mas eficiente. Ahora comparado con mi carrera es sumamente util, ya que hacer un programa que resuelva el problema en el menor tiempo, es el mejor. Poniendolo de otra forma, tu seras contratado, no el.

Calcular el camino mas corto de "1" a cualquier nodo









miércoles, 19 de mayo de 2010

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







domingo, 9 de mayo de 2010