Grafos

Grafos#

Objetivos#

  • Comprender la terminología básica de los grafos.

  • Aprender las diferentes formas de representación de grafos en programación.

  • Implementar grafos en Java utilizando diferentes representaciones.

  • Identificar aplicaciones prácticas de los grafos en problemas de la vida real.

  • Desarrollar habilidades para manipular y recorrer grafos.

Introducción#

Muchos problemas del mundo real pueden resolverse mediante algoritmos gráficos.

Los grafos son estructuras de datos fundamentales en ciencias de la computación que permiten modelar relaciones entre distintos elementos. Un grafo está compuesto por nodos (o vértices) y aristas (o enlaces), que conectan estos nodos. Los grafos son ampliamente utilizados en diversas aplicaciones, desde redes de transporte hasta algoritmos de redes sociales y análisis de redes.

https://www.researchgate.net/profile/Prohollad-Sarkar-2/publication/321846685/figure/fig1/AS:572036225683456@1513395472028/Graph-theory-analysis-in-social-network-Image-courtesy-of-5.png

Figura 67 Ejemplo de un grafo en redes sociales. Imagen tomada de A Comprehensive Survey of Time Series Anomaly Detection in Online Social Network Data - ResearchGate.#

Origen#

¿Cómo surgen los grafos?#

El estudio de los problemas de grafos se conoce como teoría de grafos. La teoría de grafos fue fundada por Leonhard Euler en 1736, cuando introdujo la terminología de los grafos para resolver el famoso problema de los Siete Puentes de Königsberg. La ciudad de Königsberg, en Prusia (actualmente Kaliningrado, Rusia), estaba dividida por el río Pregel. En el río había dos islas. La ciudad y las islas estaban conectadas por siete puentes, como se muestra en la Figura 28.2a. La pregunta es: ¿se puede dar un paseo, cruzar cada puente exactamente una vez y volver al punto de partida? Euler demostró que no es posible.

../images/Figure28.2.png

Figura 68 El problema de los siete puentes de Königsberg.#

Solución al problema de Königsberg#

Para establecer una prueba, Euler primero abstrajo el plano de la ciudad de Königsberg eliminando todas las calles, produciendo el esquema que se muestra en la Figura 28.2a un punto, llamado vértice o nodo, y cada puente con una línea, llamada arista, como se muestra en la Figura 28.2b. Esta estructura con vértices y aristas se denomina grafo.

Visualización#

Herramientas para visualizar los grafos:

Aplicaciones#

Los grafos se utilizan en muchos campos, incluyendo:

  • Redes de comunicación: Modelan redes de computadoras o Internet.

  • Mapas y rutas: Representan conexiones entre ubicaciones.

  • Redes sociales: Modelan relaciones entre personas.

  • Inteligencia artificial: Representan grafos de búsqueda en IA.

  • Sistemas de recomendaciones: Modelan preferencias de usuario y relaciones entre productos.

Recursos Adicionales#

Tutoriales#

Videos#