Cesta
0
0,00 COP
ACTIVIDAD 7 GRAFOS
Introducción a grafos de JAVIER OSPINA MORENO
Actividad:
1. Definir que es un grafo
En primera instancia debemos entender que es un grafo. Un grafo es una composición de un conjunto de objetos conocidos como nodos que se relacionan con otros nodos a través de un conjunto de conexiones conocidas como aristas.
Los grafos permiten estudiar las relaciones que existen entre unidades que interactúan con otras.
Podemos representar diversas situaciones o elementos con grafos. Estos son extraordinariamente útiles en situaciones complejas, es por esto, que es común conseguir la implementación de análisis de grafos en estudios de ciencias exactas, ciencias sociales y en aplicaciones informáticas.
Veamos a continuación los tipos de grafos que podemos implementar.
Grafo dirigido
Grafos etiquetados
Aporte personal: Los grafos son fundamentales en la teoría de redes, ya que permiten modelar y analizar problemas de la vida real, como el tráfico en carreteras, la conectividad en redes sociales o la optimización de rutas en logística. Al representar los elementos y sus relaciones de manera visual, facilitan la comprensión de la estructura subyacente en un sistema complejo. Además, el uso de algoritmos específicos para grafos, como el de búsqueda en profundidad o en anchura, ayuda a resolver problemas relacionados con la búsqueda de caminos óptimos o la detección de ciclos en un sistema.
Rochina, P. (2017, 6 septiembre). El análisis de redes sociales mediante la teoría de grafos. Canal Informática y TICS. https://www.inesem.es/revistadigital/informatica-y-tics/teoria-grafos/
Aporte personal: El video me ha permitido comprender mejor los conceptos básicos de los grafos. Me ha sorprendido la diversidad de aplicaciones que tienen los grafos, desde la logística hasta la biología. En particular, me ha interesado la aplicación de los grafos para modelar redes sociales. También me ha llamado la atención la importancia de la conectividad en los grafos, ya que determina si es posible llegar de un vértice a otro. En general, creo que los grafos son una herramienta poderosa que se puede utilizar para modelar una amplia variedad de situaciones del mundo real.
2. ¿Que uso se le dan a los grafos?
Los grafos son estructuras matemáticas que modelan relaciones y conexiones entre objetos. Se utilizan en una amplia variedad de aplicaciones, tales como:
Redes sociales: Para representar amistades o conexiones entre personas.
Optimización de rutas: En mapas de carreteras o redes de transporte.
Algoritmos de búsqueda: En inteligencia artificial y análisis de datos.
Circuitos electrónicos: Para modelar conexiones entre componentes.
Bioinformática: En análisis de secuencias de ADN y redes de proteínas.
Aporte personal: Los grafos son esenciales en la informática y la ciencia para modelar problemas complejos, representando nodos conectados por aristas. Tienen aplicaciones prácticas en diversos campos, como optimizar rutas de transporte, analizar redes sociales, y resolver problemas en biología computacional, como el mapeo de secuencias de ADN. Además, son útiles en algoritmos de búsqueda y navegación, facilitando soluciones a problemas de conectividad y flujo de datos. La versatilidad de los grafos permite abordar una amplia gama de desafíos en la teoría de redes y sistemas interconectados.
Introducción a Amazon Neptune. (s. f.-b). [Vídeo]. Amazon Web Services, Inc. https://aws.amazon.com/es/nosql/graph/
https://www.youtube.com/watch?v=dP7-gXXXiaM
Aporte personal. El video trata sobre las aplicaciones de la teoría de grafos en la vida real. La teoría de grafos es una rama de las matemáticas que se utiliza para modelar y resolver problemas complejos. Se utiliza en una amplia variedad de campos, como la logística, la traducción de idiomas, el diseño de redes, la optimización, la investigación operativa, el desarrollo de sensores en robótica, la genética y otros.
3. ¿Como se pueden clasificar los grafos?
Los grafos pueden clasificarse de diversas maneras, dependiendo de las características de sus vértices, aristas y la relación entre ellos.
Según la dirección de las aristas:
Grafos dirigidos:
Se utilizan para modelar relaciones asimétricas, como flujos de información, jerarquías, o procesos secuenciales.
Esto significa que la relación entre dos vértices no es simétrica.
Las aristas tienen una dirección específica, representada por una flecha.
Wikipedia contributors. (2024, 8 octubre). Directed graph. Wikipedia. https://en.wikipedia.org/wiki/Directed_graph#/media/File:Directed_graph_no_background.svg
Grafos no dirigidos:
-Las aristas no tienen dirección, simplemente conectan dos vértices.
-La relación entre dos vértices es simétrica.
-Se utilizan para modelar relaciones simétricas, como redes sociales, mapas de carreteras, o moléculas químicas.
Wikipedia contributors. (2024, 8 octubre). Directed graph. Wikipedia. https://en.wikipedia.org/wiki/Directed_graph#/media/File:Directed_graph_no_background.svg
Aporte personal: La clasificación de los grafos me parece una herramienta fundamental para abordar problemas complejos de manera eficiente. Al identificar las características específicas de un grafo, podemos seleccionar los algoritmos y técnicas más adecuados para su análisis. Es fascinante cómo un mismo concepto matemático puede modelar realidades tan diversas, desde redes sociales hasta rutas de transporte. Me gustaría profundizar en la aplicación de grafos ponderados para resolver problemas de optimización, como encontrar la ruta más corta en una red o el árbol de expansión mínimo.
Aporte personal: La clasificación de los grafos es un tema fascinante que me ha permitido comprender mejor la estructura y las propiedades de las redes. Me ha sorprendido la diversidad de tipos de grafos y cómo pueden modelar diferentes situaciones del mundo real. En particular, me ha interesado la aplicación de los grafos ponderados para resolver problemas de optimización, como encontrar la ruta más corta en una red o el árbol de expansión mínimo. También me ha llamado la atención la importancia de la conectividad en los grafos, ya que determina si es posible llegar de un vértice a otro. En general, creo que la clasificación de los grafos es una herramienta fundamental para el análisis de redes y que tiene un gran potencial para ser aplicada en diversos campos, como la informática, la biología y la economía.
4. ¿Como se pueden representar los grafos?
Una guía visual y conceptual
Los grafos, como estructuras matemáticas que representan relaciones entre objetos, pueden ser representados de diversas formas. Cada representación tiene sus ventajas y desventajas, y la elección de una u otra dependerá del tipo de grafo y del problema que se esté resolviendo.
Representaciones gráficas
Diagramas: Esta es la forma más intuitiva de representar un grafo. Los vértices se dibujan como puntos o círculos, y las aristas como líneas que conectan estos puntos. Para grafos dirigidos, se utilizan flechas para indicar la dirección de la relación.
Representaciones matriciales
- Matriz de adyacencia: Esta es una matriz cuadrada donde las filas y columnas representan los vértices. Si existe una arista entre dos vértices, la celda correspondiente en la matriz contiene un 1, de lo contrario, contiene un 0. Para grafos ponderados, el valor de la celda puede representar el peso de la arista.
imagen captada de video https://www.youtube.com/watch?v=9C2cpQZVRBA
- Listas de adyacencia: Para cada vértice, se crea una lista que contiene los vértices adyacentes. Esta representación es más eficiente en términos de espacio para grafos dispersos (con pocas aristas).
GeeksforGeeks. (2024, 5 octubre). Graph and its representations. GeeksforGeeks. https://www.geeksforgeeks.org/graph-and-its-representations/
Nota: Recuerde que cada pregunta debe ir acompañada de:
- Los enlaces de donde consulto la información (normas Apa) .
- De un aporte personal con sus propias palabras de lo que entendió de lo consultado.
- De una imagen que tenga relación con el tema o pregunta con su respectivo enlace (normas Apa)
- Insertar un video video (youtube) que explique o aclare la pregunta con su enlace respectivo (normas Apa)
- Debajo del video realizar un resumen de lo que dice o explica el autor del video.
Descargar las siguientes diapositivas para la conceptualización, practica y diseño de Grafos...
Nota: Realizar el ejercicio propuesto al final de las Diapositivas..
Contesta las siguientes preguntas dando una explicación corta:
- Qué relación hay entre la estructura árbol y la estructura grafo? Puede ser un grafo un árbol?
- Es un grafo una estructura recursiva? Explique
- Para qué tipo de problemas se utiliza la estructura grafo? De dos ejemplos
- Como se puede representar la estructura grafo? Explique
- Construya dos grafos: Uno dirigido y otro no dirigido
Solución
- La relación entre la estructura de árbol y la estructura de grafo es que ambos son tipos de estructuras de datos utilizadas para representar relaciones entre elementos
- Un grafo puede ser una estructura recursiva dependiendo de cómo se defina y se utilice. Por ejemplo, si un grafo contiene nodos que pueden apuntar a otros nodos dentro del mismo grafo, entonces sí podría considerarse una estructura recursiva.
- Rutas más cortas: En redes de transporte o comunicación, encontrar la ruta más corta entre dos puntos.
Redes sociales: Analizar la estructura de una red social para identificar comunidades, influenciadores, etc. - Lista de adyacencia: Donde cada nodo tiene una lista de los nodos adyacentes a él.
Matriz de adyacencia: Una matriz donde cada fila y columna representan nodos, y los valores indican si hay una conexión entre esos nodos.
Recorrer grafos en anchura y en profundidad. (2020, 9 noviembre). [Vídeo]. YouTube. https://www.youtube.com/watch?v=HelpfhBel_k&t=82s&ab_channel=martino
Dar clic en el siguiente enlace para acceder a los recorridos a través de los grafos