CONCEPTOS FUNDAMENTALES DE LA TEORIA DE GRAFICOS

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

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.

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.

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

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 (

• 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

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