Grafos Eulerianos Y Hamiltonianos.Docx

1. Introducción
La palabra algoritmo viene de Al-Khowarizmi sobrenombre del célebre matemático
Mohamed Ben Musa. Hoy en día, el algoritmo es una forma ordenada de describir
los pasos para resolver problemas. Es una forma abstracta de reducir un problema
a un conjunto de pasos que le den solución.
En el siguiente trabajo pretendemos presentar una serie de concepto y definiciones propios delestudio de los Algoritmos, su análisis y diseño.
En el mismo podremos encontrar los conceptos de algoritmo y algunos de sus componentes, análisis y diseño. También veremos los diferentes tipos de formas y tamaños o medidas en que se pueden almacenar y representar los datos y estructuras en un algoritmo o programa. En ese mismo orden encontraremos las diferentes técnicas para diseñarlos como son elmétodo de la fuerza bruta, el voraz, divide y vencerás, programacióndinámica, de vuelta atrás, entre otros.
De igual forma podremos ver las definiciones y algunas características, reglas, normas, tipos de algoritmos de búsqueda y ordenación así como sus aplicaciones.
Finalmente veremos los que es la verificación y derivación de programas, donde daremos los conceptos básicos de semántica y sustipos haciendo mayor énfasis en la semántica axiomática, la recursividad e iteración, los diseños de estos últimos, así como los típicos ciclos utilizados en algoritmos y programas y los paso a tener en cuenta al momento de desarrollar un algoritmo iterativo o recursivo.


Leer más: http://www.monografias.com/trabajos11/alcom/alcom.shtml#ixzz2J4b3aTrw





GRAFOS EULERIANOS Y HAMILTONIANOSExisten todavía algunas familias de grafos que se derivan del concepto de grafos conexos. Este es el caso de los grafos eulerianos y los grafos hamiltonianos. Estas familias de grafos nos permiten resolver el famoso problema de los puentes de Königsberg:
¿cuándo es posible hacer un recorrido de una figura (en este caso de un grafo múltiple) sin pasar dos veces por la misma línea o por elmismo vértice?

En la fig. 3.10 tenemos dos grafos G1 y G2; es posible recorrer uno de ellos sin repetir ninguna línea, pero el otro no. ¿Cuál es cuál? Es evidente que el grafo G1 no puede ser recorrido sin repetir alguna de sus líneas, mientras que el grafo G2 sí.


Fig 3.10
I. GRAFOS EULERIANOS

Recorrido cerrado

Cubre todas las líneas de un grafo, comenzando y terminando en un mismovértice, recorriendo sin repetición y en forma continua todas las líneas de un grafo G cualquiera. Cuando tal recorrido existe, se denomina euleriano y un grafo que se puede trazar mediante un recorrido euleriano se llama grafo euleriano. En la fig. 3.11, G1 es obviamente un grafo euleriano; G2 no lo es, a pesar de que se puede trazar continuamente, ya que el recorrido comienza y termina en vérticesdistintos; finalmente, G3 no es un grafo euleriano, porque no se puede trazar continuamente.


Fig. 3.11
Teorema 3.2

Diremos que un grafo G es la unión disjunta de ciclos, si podemos descomponer a G como la unión de ciclos que no tienen líneas en común, aunque se permite que tengan, al menos, un vértice en común.


II. GRAFOS HAMILTONIANOS

¿Cuándo es posible hacer un recorrido enun grafo que pase por cada vértice exactamente una vez y termine en el vértice original?
O en otras palabras, ¿cuándo un grafo tiene un ciclo cerrado que contenga a todos sus vértices?

Cuando existe tal ciclo, lo llamaremos ciclo hamiltoniano y un grafo que posea un ciclo hamiltoniano se llama grafo hamiltoniano.

Un ciclo puro Cp es evidentemente hamiltoniano; el grafo de la fig. 3.14también. En efecto, el ciclo v1v2... v7v1 representa un ciclo hamiltoniano del grafo G.



CAMINO MAS CORTO: ALGORITMO DE DIJKSTRA
El algoritmo de dijkstra determina la ruta más corta desde un nodo origen hacia los demás nodos para ello es requerido como entrada un grafo cuyas aristas posean pesos. Algunas consideraciones:
 Si los pesos de mis aristas son de valor 1, entonces bastará con...