CONCEPTOS FUNDAMENTALES DE LA TEORIA DE GRAFICOS

More like this

-Fratelli Tutti- & El dilema de las redes sociales

by Sebastian De Valdenebro

Unidad 2. Posicionamiento Digital

by Fundación Didáctica XXI

El derecho a la vida

by María Belén Astudillo

MODELO SISTEMICO Y PSICOLOGIA SOCIAL

by July Paola Molina Ramirez

CONCEPTOS FUNDAMENTALES DE LA TEORIA DE GRAFICOS

UN POCO DE HISTORIA

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

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?

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

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

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.

ARBOL DE PESO MINIMO es aquel que obtenemos en un grafo conexo y sin ciclos.

ARBOLES Un árbol es una gráfica conexa que no contiene ciclos.

PARTES DE UN ARBOL

GRADO

ALTURA

NIVEL DE NODO

INTERIOR

HOJA

RAIZ

HERMANO

HIJO

PADRE

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

CICLO

TRAYECTORIA

PASEO