Actividad 7-Grafos
Introducción a grafos de JAVIER OSPINA MORENO
Actividad:
1. Definir que es un grafo
2. ¿Qué uso se le dan a los grafos?
3. ¿Cómo se pueden clasificar los grafos?
4. ¿Cómo se pueden representar los grafos?
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.
Respuesta:
1. ¿Qué es un grafo?
Un grafo es una estructura matemática y computacional formada por un conjunto de nodos (o vértices) y aristas (o conexiones) que unen esos nodos. Sirve para representar relaciones entre elemento
Explicación del video:
El video explica que un grafo está compuesto por nodos y aristas, mostrando cómo se conectan entre sí. También menciona ejemplos de la vida real como redes sociales y mapas, donde cada punto representa algo y las conexiones indican relaciones.
Aporte Personal:
Entendí que los grafos son una forma de representar relaciones entre cosas, como amigos en redes sociales o ciudades en un mapa, lo que los hace muy útiles para organizar información.
2. ¿Qué uso se le dan a los grafos?
Los grafos se usan para representar y analizar relaciones en diferentes áreas.
Wikipedia. (2023). Graph theory applications. https://en.wikipedia.org/wiki/Graph_theory
Explicacion de video:
El video muestra que los grafos se utilizan en redes sociales, sistemas de navegación (GPS), internet y videojuegos. Explica que ayudan a encontrar rutas más cortas, conexiones y optimizar procesos.
Aporte personal
Comprendí que los grafos no solo son teoría, sino que se usan mucho en la vida diaria, como en Google Maps o Instagram, para conectar información y encontrar caminos más eficientes.
3. ¿Cómo se pueden clasificar los grafos?
Los grafos se clasifican según sus características:
- Dirigidos: las aristas tienen dirección
- No dirigidos: no tienen dirección
- Ponderados: tienen valores (peso)
- No ponderados: no tienen peso
Explicación de video:
El video explica los diferentes tipos de grafos y cómo se diferencian. Muestra ejemplos claros de grafos dirigidos, no dirigidos y ponderados, resaltando cuándo usar cada uno.
Aporte personal
Aprendí que no todos los grafos son iguales, y que su clasificación depende de cómo se conectan los nodos. Esto es importante porque cada tipo sirve para resolver problemas distintos.
4. ¿Cómo se pueden representar los grafos?
Los grafos se pueden representar de varias formas:
-Lista de adyacencia: lista de vecinos de cada nodo
-Matriz de adyacencia: tabla que muestra conexiones
-Lista de aristas: conjunto de conexiones
Explicación del video:
El video explica cómo representar grafos usando matrices y listas. Muestra ejemplos de cómo se construyen y cuándo conviene usar cada método según el problema.
Aporte personal
Entendí que la forma de representar un grafo depende de lo que se necesite hacer con él, ya que algunas representaciones son más rápidas o más fáciles de usar que otras
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?
Respuesta:
Un árbol es un tipo especial de grafo. Es un grafo conectado y sin ciclos.
Sí, un grafo puede ser un árbol, siempre que cumpla esas condiciones.
Es un grafo una estructura recursiva? Explique
Respuesta:
Sí. Un grafo puede verse como una estructura recursiva porque está formado por nodos que se conectan entre sí, y cada nodo puede tener conexiones a otros nodos que a su vez tienen más conexiones.
Para qué tipo de problemas se utiliza la estructura grafo? De dos ejemplos
Respuesta:
Se usan para representar relaciones y conexiones.
Ejemplos:
- Redes sociales (usuarios conectados como amigos)
- Rutas de transporte (ciudades conectadas por caminos)
Como se puede representar la estructura grafo? Explique
Respuesta:
Se puede representar de varias formas:
- Matriz de adyacencia: una tabla donde se indica si hay conexión entre nodos.
- Lista de adyacencia: cada nodo guarda una lista de sus vecinos.
Construya dos grafos: Uno dirigido y otro no dirigido
Respuesta:
Grafo dirigido (las conexiones tienen dirección):
A → B → C
A → C
Grafo no dirigido (las conexiones no tienen dirección):
A — B
B — C
A — C
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