Actividad 7

Definir que es un grafo

Un grafo es un modelo para representar relaciones entre elementos de un conjunto.

Gráficamente se representa como un conjunto vértices o nodos unidos por líneas que representan las aristas.

es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.

¿Qué uso se le dan a los grafos?

Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que se pueden obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.

¿Cómo se pueden clasificar los grafos?

los grafos se pueden definir de la siguiente forma:

grafos no-dirigido: Un grafo no dirigido es un tipo de grafo en el cual las aristas representan relaciones simétricas y no tienen un sentido definido, en eso se diferencia de los dirigidos que ellos si tienen artistas y relaciones simétricas definidas.

Grafo dirigido: Son grafos a los cuales se le añade una orientación a las aristas, representada gráficamente por una flecha

Grafo etiquetado: Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.

Grafo aleatorio. Grafo cuyas aristas están asociadas a una probabilidad.

Hipergrafo: Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.

Grafo infinito: Grafos con conjunto de vértices y aristas de cardinal infinito.

¿Cómo se pueden representar los grafos?

Hay varias formas de representar gráficos, cada una con sus ventajas y desventajas. Algunas situaciones o algoritmos que queremos ejecutar que toman un gráfico como entrada requieren una representación, mientras que otros requieren una representación diferente. Aquí, examinaremos tres métodos para representar gráficos. Veremos tres criterios. Una es cuánta memoria o espacio necesitamos en cada representación. Usaremos notación asintótica para esto.

¡Sí, podemos usar la notación asintótica para otros fines además de representar el tiempo de ejecución! En realidad, es una forma de caracterizar una función, que puede describir el tiempo de ejecución, la cantidad de espacio requerido o algún otro recurso.

Los otros dos criterios que utilizaremos están relacionados con el tiempo. Uno es cuánto tiempo lleva determinar si un borde dado está en el gráfico.

DESCARGAR grafos.ppsx

Conclusión

Se puede decir que los grafos son un conjunto de nodos o de llamados vértices donde los arcos cada uno tiene que tener un par de nodos, aun mas importante decimos tenemos que tener en cuenta que los grafos se pueden denominar como arcos dirigidos, el grafo se denomina grafo directo, dirigido o dígrafo.

Cuando representamos los grafos tenemos que tener en cuenta que hay dos tipos que son los secuenciales que contiene los adyacentes y las enlazadas que contienen las listas encadenadas, consultando se nos da a evidenciar que un grafo puede estar dirigidos en varios nodos pero si los nodos están conectados podemos hablar de grafos conexos

Representar grafos (artículo) | Algoritmos. (2020). Khan Academy. https://es.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

Pérez, G. M. C.-. (2019). Definición | Grafos. grafos. https://163.10.22.82/OAS/estructuras_de_grafos/definicin.html

Gala, G. F. J. (2015, 16 febrero). Estructuras de datos en red: los grafos. Urban Tecno. https://urbantecno.com/android/grafos#:%7E:text=Tipos%20de%20grafos,-Grafo%20simple.%20o&text=Es%20la%20definici%C3%B3n%20est%C3%A1ndar%20de,de%20esta%20categor%C3%ADa%20de%20grafos.

representacion de grafos. (2011, 21 abril). [Vídeo]. YouTube. https://youtu.be/cNAkUZaiDo4

Clasificación de grafos. (2021, 26 junio). [Vídeo]. YouTube. https://youtu.be/0cQk2xn0ktE

uso de los grafos. (2021, 26 mayo). [Vídeo]. YouTube. https://youtu.be/mZMJJV6jDec

Taller recorrido de grafos

DESCARGAR TAL...LASE.xlsx