CONCEPTOS FUNDAMENTALES DE LA TEORIA DE GRAFICOS
CAMINOS Secuencia de vértices dentro de un grafo tal que exista una arista entre cada vértice y el 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
PASEO
TRAYECTORIA
CICLO
ARBOLES Un árbol es una gráfica conexa que no contiene ciclos.
PARTES DE UN ARBOL
PADRE
HIJO
HERMANO
RAIZ
HOJA
INTERIOR
NIVEL DE NODO
ALTURA
GRADO
ARBOL DE PESO MINIMO es aquel que obtenemos en un grafo conexo y sin ciclos.
GRAFOS Los grafos permiten estudiar las interrelaciones entre unidades que se encuentran en interacción. Son diagramas que si se interpretan en forma adecuada proporcionan información, como por ejemplo los mapas, diagramas de círculos o de flujos, entre otros.
APLICACIONES DE LA ACTUALIDAD
• Redes sociales. (Adecuado almacenamiento de datos para uso)
• Química (Modelado de redes de carbono)
• Biología molecular (Para generar modelos de proteínas y mapas genómicos
• Ciencias de la Computación (Para generar nuevos algoritmos)
• Redes de comunicaciones, diseño, ruteo
• Problemas de distribución y ruteo de vehículos.
• Planificación de la producción.
• Descifrado de Códigos
• Ingeniería de Software
• Bases de datos
• Biología Computacional
UN POCO DE HISTORIA
El trabajo de Leonhard Euler, en 1736, sobre el problema de los puentes de Königsberg es considerado como uno de los primeros resultados de la Teoría de gráficas
El problema de los puentes de Königsberg. A esta ciudad la cruza el río Pregel creando dos islas. ¿Se puede recorrer toda la ciudad pasando una sola vez por todos y cada uno de los 7 puentes que unen la parte insular de la ciudad con el resto?
La solución de Euler. El famoso matemático abstrajo los detalles de la forma de la ciudad y sus puentes para quedarse con la conectividad, dando lugar a una de las primeras gráficas. El grado de todos los vértices es impar, lo que implica que es imposible recorrerlos todos pasando una sola vez por cada uno