Actividad 7

Grafo

Actividad

1. Definir que es un grafo

Los grafos son una estructura de datos no lineal parecida a la de los arboles, pero este seria un árbol sin las leyes de acomodo que rigen a un árbol normal. También están conformados de nodos o también nombrados vértices los cuales son registros con datos y al menos un apuntador a otro nodo, y de aristas, las cuales son las conexiones que existen de un nodo a otro.

Hernández, J. L. B. (2021, 16 diciembre). Estructura de datos: Grafos - José Luis Banda Hernández - Medium. Medium. https://a01610329.medium.com/estructura-de-datos-grafos-ad9e7d91a79b

Aporte: Los grafos son una estructura de datos no lineal similar a los árboles, pero se diferencian en que son árboles que no siguen las leyes de acomodo que regulan a los árboles tradicionales. Están compuestos por nodos, también llamados vértices, que son registros con datos y al menos un apuntador a otro nodo. Además, los grafos incluyen aristas, que son las conexiones que existen entre los nodos.

Makeitrealcamp. (s. f.-b). guides/algoritmos/estructuras-de-datos.md at master · makeitrealcamp/guides. GitHub. https://github.com/makeitrealcamp/guides/blob/master/algoritmos/estructuras-de-datos.md

Arnau Gómez. (2022, 12 abril). GRAFOS: explicación con DIBUJOS | Estructuras de datos 4 [Vídeo]. YouTube. https://www.youtube.com/watch?v=w6Pkf5UloEI

Resumen: Se explican los grafos como estructuras de datos que representan ciudades y carreteras mediante nodos y aristas. Se detalla cómo construir una matriz de adyacencia para representar la conexión entre nodos, facilitando la visualización y análisis de relaciones. Los grafos tienen múltiples aplicaciones en diversos problemas.

2. ¿Que uso se le dan a los grafos?

colaboradores de Wikipedia. (2024, 31 julio). Grafo. Wikipedia, la Enciclopedia Libre. https://es.wikipedia.org/wiki/Grafo

https://www.oracle.com/co/autonomous-database/what-is-graph-database/#graph-database-types

Aporte: Los grafos son una herramienta fundamental en la informática y las matemáticas, ya que permiten modelar relaciones complejas entre diferentes entidades. Su flexibilidad, al no estar sujetos a un orden específico como los árboles, los hace ideales para representar redes sociales, rutas en mapas y conexiones en sistemas informáticos.

Parra, A. (2016b, mayo 2). GoConQR - Teoría de grafos. GoConqr. https://www.goconqr.com/mapamental/5295814/teoria-de-grafos

El Taller De TD. (2022, 16 julio). Teoría de GRAFOS en INFORMÁTICA: Que es un grafo, Tipos de Grafos, como representarlos y ejemplos [Vídeo]. YouTube. https://www.youtube.com/watch?v=F5Xjpg0-NhM

Resumen : Explica la teoría de grafos es fundamental en informática para modelar relaciones entre conjuntos de datos. Existen diversos tipos de grafos, como no dirigidos, dirigidos y con pesos, que tienen múltiples aplicaciones, incluyendo el protocolo criptomoneda .

3. ¿Como se pueden clasificar los grafos?

1. Por dirección

Grafos dirigidos: Las aristas tienen una dirección específica, lo que significa que la relación entre los vértices es unidireccional.
Grafos no dirigidos : Las aristas no tienen dirección, lo que implica que la relación entre los vértices es bidireccional.

2. Por cantidad de aristas:

Grafos simples : Permiten solo una arista entre dos vértices.
Multigrafos : Aceptan múltiples aristas entre los mismos dos vértices, lo que permite representar relaciones más complejas.

3.Por características adicionales:

Grafos etiquetados : Cada vértice o arista puede tener una etiqueta o atributo que los identifique de manera única.
Grafos ponderados: Las aristas tienen un peso o costo asociado, lo que permite realizar análisis más complejos, como encontrar el camino más corto.
Grafos aleatorios: Las conexiones entre los vértices se generan de manera aleatoria.

4.Por conectividad:

Grafo conexo : En un grafo no dirigido, existe al menos un camino entre cada par de vértices.
Grafo fuertemente conexo: En un grafo dirigido, existe un camino dirigido entre cada par de vértices.

5.Otros tipos:

Hipergrafos: Permiten que una sola arista conecte múltiples vértices.
Grafos infinitos: No tienen un número limitado de vértices o aristas.

Estructura de datos de grafos: Conceptos, Tipos | StudySmarter. (s. f.). StudySmarter ES. https://www.studysmarter.es/resumenes/ciencias-de-la-computacion/estructuras-de-datos/estructura-de-datos-de-grafos/

Aporte: Los grafos son estructuras matemáticas versátiles que se pueden clasificar de diversas maneras según sus propiedades y características. En primer lugar, se pueden clasificar por dirección en grafos dirigidos y no dirigidos, lo que afecta cómo se representan las relaciones entre los vértices. Además, la cantidad de aristas también determina la clasificación en grafos simples y multigrafos, permitiendo diferentes representaciones de relaciones.

Platzi: Plataforma de aprendizaje profesional online. (s. f.). https://platzi.com/clases/1319-discretas/12221-teoria-de-grafos/

Pull Request. (2024, 3 octubre). Grafos | Parte 1 | Estructuras de datos con GO [Vídeo]. YouTube. https://www.youtube.com/watch?v=fx63gLS6QFQ

Resumen : Explica una introducción a los grafos, estructuras que representan relaciones entre objetos mediante nodos y aristas. Se explican tipos de grafos (dirigidos, no dirigidos y ponderados) y sus implementaciones en programación, así como operaciones básicas como agregar o eliminar vértices y aristas, y calcular caminos más cortos.

4. ¿Como se pueden representar los grafos?

Lista de aristas

Una forma sencilla de representar un grafo es solo una lista, o un arreglo, de |E| aristas, a la que llamamos una lista de aristas. Para representar una arista, solo tenemos un arreglo de dos números de vértices, o un arreglo de objetos que contienen los números de vértices sobre los que inciden las aristas. Si las aristas tienen pesos, agrega ya sea un tercer elemento al arreglo o más información al objeto, que dé el peso de la arista. Como cada arista contiene solo dos o tres números.

Matriz de adyacencia

Para un grafo con |V| vértices, una matriz de adyacencia es una matriz de |V| times |V| de ceros y unos, donde la entrada en el renglón "i" y la columna "j"es 1 si y solo si la arista (i, j) está en el grafo. Si quieres indicar un peso de la arista, ponlo en la entrada del renglón "i" , columna" j" y reserva un valor especial (tal vez null) para indicar una arista ausente.

Listas de adyacencia

Representar un grafo con listas de adyacencia combina las matrices de adyacencia con las listas de aristas. Para cada vértice " i ", almacena un arreglo de los vértices adyacentes a él. Típicamente tenemos un arreglo de |V| listas de adyacencia, una lista de adyacencia por vértice.

Khan Academy. (s. f.). https://es.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

Aporte: Los grafos se pueden representar de diversas maneras, siendo tres de las más comunes la lista de aristas, la matriz de adyacencia y la lista de adyacencia. La lista de aristas consiste en un conjunto de pares de vértices que representan cada una de las conexiones (o aristas) en el grafo, lo que es útil para grafos no dirigidos o dirigidos por igual. La matriz de adyacencia utiliza una tabla bidimensional donde las filas y columnas representan los vértices; un valor de uno indica que existe una arista entre los vértices correspondientes, mientras que un cero indica lo contrario, facilitando la verificación de conexiones. Por otro lado, la lista de adyacencia presenta cada vértice junto con una lista de sus vértices vecinos, lo que resulta en un uso de memoria más eficiente para grafos esparcidos.

CHOCHY. (2021b, julio 24). Representación de grafos [Vídeo]. YouTube. https://www.youtube.com/watch?v=gbb2Mgvl6yk

Resumen : Explica la representación de las tres formas convencionales de representar grafos: matriz de adyacencia, matriz de incidencia y lista de adyacencia. Se explica cómo cada una representa las conexiones entre nodos y aristas, además de cómo se construyen y utilizan en grafos dirigidos y no dirigidos, así como en grafos ponderados.