Grafos y algoritmos

GRAFOS Y ALGORITMOS

[pic]

I. INTRODUCCION
La importancia teórica del Tema es debido a la gran cantidad de problemas existen en el área, todavía en base de estudio. existe un creciente número de publicaciones y artículos especializados y una gran cantidad de grupos de investigación en universidades dedicadas a losgrafos y algoritmos.
Se trata de una materia actual, todavía en formación. Es un tema relevante desde el punto de vista práctico tanto en Computación como en Matemática aplicada. Existe una gran cantidad de problemas prácticos que pueden ser tratados mediante un modelamiento de Grafos y luego resueltos con un programa de Computador, implementando un algoritmo apropiado.El tema será tratado desde un punto de vista computacional o sea los algoritmos son desarrollados considerando un enfoque Computacional, es decir algoritmos son formulados siempre considerando una posible implementación posterior en computador. En este sentido la eficiencia del tiempo y espacio de un proceso son factores básicos para su evaluación. Simultáneamente el tema espresentado sobre un tratamiento matemático, por ejemplo en la verificación de la corrección de un algoritmo o en la determinación de su eficiencia.
Entonces en este curso se presentará principalmente las técnicas en Grafos y Algoritmos de aplicación. Por lo tanto, en el primer capítulo se presenta una breve descripción de la teoría de Grafos, luego la descripción de técnicaselementales, posteriormente la busca en Grafos con los métodos más utilizados en problemas algoritmicos, en el siguiente capítulo, se considera la presentación de técnicas utilizadas en optimización Combinatorial y finalmente se describen los principios de la teoría de NP-Completitud.
 
 
 
I. 1Consideraciones Preliminares.
 
Es importante recordar que la idea es resolver problemas algoritmicos en Grafos, teniendo siempre en cuenta la eficiencia Computacional.
El objetivo principal es encontrar si es posible algoritmos eficientes para resolver un determinado problema en Grafos.
Existen diferencias conla teoría de Grafos, ya que existen problemas no algoritmos en Grafos en que el concepto de eficiencia no tiene sentido en cambio la preocupación por la eficiencia en el área de algoritmos implican la formulación de problemas algoritmos en Grafos que sin duda no interesan a la teoría. A pesar de lo anterior, es muy común el hecho que una posible mejora en la eficiencia de un algoritmo para undeterminado problema en Grafos solo puede ser obtenida a través de un buen conocimiento teórico del problema, o sea en general algoritmos más eficientes significan el uso de procesos cuya eficiencia es independiente de aspectos teóricos en Grafos.
En realidad los inicios de la teoría de Grafos lo constituyó un problema algoritmico, es un problema donde la solución salió apartir de la Construcción de un algoritmo eficiente, se trata del : "Problema de Puente de Königsherg", Euler 1936.
 
[pic]
 
El problema es encontrar una ruta por los puentes saliendo desde una zona y retornando a la misma y pasando una sola vez por cada puente. Euler demostró que no existe tal ruta alutilizar un modelo de grafos para una generalización del problema. El demostró que existe la ruta deseada sólo cuando a cada región llega un número par de puentes. Esto fue considerado como el 1er teorema en la teoría de Grafos (por más de 200 años) pero en realidad poco se ha alcanzado posteriormente. A mediados del siglo XIX, tres estudios aislados sobre el tema han presentado interés; estos son:...