Teoria de Grafos

INTRODUCCION
Como ya se sabe el estudio de los grafos abarca desde lo matemático hasta lo computacional actualmente en el mundo existen diversos tipos de grafos todos ellos para hacer nuevas o mejorara las tareas de cada uno de estos.
Gracias a la teoría de grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales. Se utiliza para diferentes áreas porejemplo, Dibujo computacional, en todas las áreas de Ingeniería.
Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos.

Para poder representar los grafos muchos autores señalan entre las estructuras más sencillas y usadas se encuentranlas listas y las matrices, aunque frecuentemente se usa una combinación de ambas. 















DESARROLLO
1.1 Introducción a grafos

El nacimiento del concepto GRAFOS se puede situar, por el año 1730, cuando Euler (matemático) se convirtió en el padre de la Teoría de Grafos al modelar un famoso problema no resuelto, llamado el "problema de los puentes de Königsberg".

Unrío con dos islas atraviesa la ciudad. Las islas están unidas, entre sí y con las orillas, a través de siete puentes. El problema consistía en establecer un recorrido que pasara una y solo una vez por cada uno de los siete puentes, partiendo de cualquier punto y regresando al mismo lugar.
Para probar que no era posible, Euler sustituyó cada zona de partida por un punto y cada puente por un arco,creando así un grafo, el primer grafo, diseñado para resolver un problema.
Mostrar que el problema no tiene solución equivale a mostrar que el grafo no puede ser recorrido según criterios determinados.
Problema genérico: dado un grafo (con múltiples líneas entre pares de puntos) encontrar un camino que recorra el grafo pasando por cada arista exactamente una vez.
Solución: El grafo debe serconexo, y en cada punto deben incidir un número par de líneas. Esta condición es suficiente para definir lo que se llama un ciclo euleriano.
A partir de Euler el modelado mediante grafos fue desarrollando esta metodología hasta convertirse en la actualidad, en una herramienta de trabajo para ciencias tan diferentes como la Física, la Química, la Sicosociología, la Economía, la Lingüística, etc. Lateoría de grafos está íntimamente relacionada con varias ramas de la Matemáticas como por ejemplo la Teoría de Conjuntos, el Análisis Numérico, Probabilidad, Topología, etc. y es la base conceptual en el tratamiento de problemas combinatorios.
La eficacia de los grafos se basa en su gran poderío de abstracción y la muy clara representación de cualquier relación (de orden, precedencia, etc.) lo quefacilita enormemente tanto la fase de modelado como de resolución del problema. Gracias a la Teoría de Grafos se han desarrollado una gran variedad de algoritmos y métodos de resolución eficaces que nos permiten tomar una mejor decisión.



1.2 Caminos y Ciclos


En Teoría de Grafos, se llama Camino a una secuencia de vértices dentro de un grafotal que exista una arista entre cada vértice yel siguiente. Se dice que dos vértices están conectados si existe un camino que vaya de uno a otro, de lo contrario estarán desconectados. Dos vértices pueden estar conectados por varios caminos. El número de aristas dentro de un camino es su longitud. Así, los vértices adyacentes están conectados por un camino de longitud 1, y los segundos vecinos por un camino de longitud 2.

FIG.1En Teoría de grafos, un Grafo ciclo o simplemente ciclo es un grafo que se asemeja a un polígono de n lados. Consiste en un camino cerrado en el que no se repite ningún vértice a excepción del primero que aparece dos veces como principio y fin del camino. Un Grafo ciclo de n vértices se denota Cn. El número de vértices en un grafo Cn es igual al número de aristas, y cada vértice tiene grado par,...