Actividad 7
1. ¿Qué 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.
O. (2020, 10 maart). Qué son los grafos. GraphEverywhere. Geraadpleegd op 23 april 2022, van https://www.grapheverywhere.com/que-son-los-grafos/
Grafo. (z.d.). [Imagen]. Wikipedia. https://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos
M. (2016, 14 september). ¿QUÉ SON LOS GRAFOS? - Nivel Básico [Video]. YouTube. https://www.youtube.com/watch?v=wKeg6tOG7qI&feature=youtu.be
Aporte personal:
A mi parecer los grafos es un tipo de arbol mas complejo, con conexiones binarios en sus nodos creando una red de datos con aristas, con el fin de hacer más eficiente el recorrido entre sus nodos.
2. ¿Qué uso se le da?
Prácticamente cualquier red puede ser modelada con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o un sistema de alcantarillados, una red de computadoras. Al visitar una página web y hacer clic a un enlace, visto como un grafo los vértices son los sitios, y cuyas aristas son lógicamente los enlaces.
Gracias a la teoría de Grafos se pueden resolver diversos problemas como por ejemplo la síntesis de circuitos secuenciales.
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 podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.
Para la administración de proyectos, utilizamos técnicas como PERT en las que se modelan los proyectos utilizando grafos y optimizando los tiempos para concretar las distintas tareas asociadas al desarrollo de un proyecto en particular.
U. (z.d.). Aplicaciones De Grafos. Estructuras de datos. Geraadpleegd op 23 april 2022, van https://estructuradedatosuniversidadincca.blogspot.com/2015/10/aplicaciones-de-grafos.html
Usos de grafos. (z.d.). [Imagen]. Usos de grafos. https://revistadigital.inesem.es/informatica-y-tics/teoria-grafos/
E. (2015, 7 mei). Aplicaciones de la Teoría de Grafos a la Vida Real (I) | UPValenciaX on edX | Course About Video[Video]. YouTube. https://www.youtube.com/watch?v=dP7-gXXXiaM&feature=youtu.be
Aporte personal:
El uso de grafos es demasiado en la vida cotidiana en la conexión o resolución dé problemas, aunque no nos demos cuenta, se ve en redes sociales, caminos de ciudades, recorridos de autobus. Todo se ve siempre con el fin de escoger la opción más efectiva para el problema que tenemos.
3. ¿ Cómo se pueden clasificar?
Grafos dirigidos y no dirigidos dependiendo del tipo de relación entre los vértices del grafo, se definen distintos tipos de grafos. Así se distinguen aristas dirigidas y no dirigidas:
Dentro de los principales tipos de grafos que podemos estudiar están los grafos dirigidos.
Éstos son una especie de grafo que cuentan con elementos clásicos de un grafo simple pero con la particularidad de que sus aristas que conectan los nodos tienen una direccionalidad clara. Adicionalmente a los grafos dirigidos tenemos los que conocemos como grafos completos.
Un grafo completo de forma similar cumple con los requisitos de un grafo simple o dirigido. La diferencia que se presenta en este tipo de grafos es que cada par de nodos debe estar interconectado entre sí con diferentes conjuntos de aristas que conforman un camino.
Por su parte los grafos conexos son aquellos que cumplen con una condición especial. Para que un grafo se considere conexo entre los nodos que lo integran deben existir "caminos simples". De esta estructuración de nodos nace lo que conocemos como árboles de grafos.
Sumado a esta clasificación tenemos los grafos etiquetados. A diferencia de los tipos de grafos anteriores, los grafos etiquetados incorporan datos en las aristas que le proporcionan peso a un grafo y estos son los más comunes en el mundo informático en el que vivimos.
O. (2021, 11 februari). Grafos | Qué son, tipos, orden y herramientas de visualización. GraphEverywhere. Geraadpleegd op 23 april 2022, van https://www.grapheverywhere.com/grafos-que-son-tipos-orden-y-herramientas-de-visualizacion/
Tipos grafos. (z.d.). [Imagen]. Tipos de grafos. https://platzi.com/clases/1319-discretas/12221-teoria-de-grafos/
M. (2016, 14 september). ¿QUÉ SON LOS GRAFOS? - Nivel Básico [Video]. YouTube. https://www.youtube.com/watch?v=wKeg6tOG7qI&feature=youtu.be
Aporte personal:
Los grafos tienen muchas formas, donde depende como se vaya implementar de acuerdo a su problema, asi se va comportar las direccion de aristas y su forma de ejecución, por eso es importante definir el grafo a usar en el problema específico.
4. ¿Cómo se pueden representar?
Las representaciones más utilizadas de representación de los grafos son:
a. Representación por matriz de adyacencia
b. Representación por listas de adyacencias.
La matriz de adyacencia es la forma más común de representación y la más directa. Consiste en una tabla de tamaño nxn, en que la que aij tendrá como valor 1 si existe una arista del vértice i al vértice j. En caso contrario, el valor será 0. Si el grafo es no dirigido hay que asegurarse de que se marca con un 1 tanto la entrada aij como la entrada aji, puesto que se puede recorrer en ambos sentidos.
6.2.- Representación de los grafos. (z.d.). mate-discretas. Geraadpleegd op 23 april 2022, van https://gabeezko.wixsite.com/mate-discretas/62--representacin-de-los-grafos
Representación de grafos. (z.d.). [Imagen]. Representación de grafos. https://fcaenlinea1.unam.mx/anexos/1566/1566_u4_anexo3.pdf
E. (2015, 7 mei). Aplicaciones de la Teoría de Grafos a la Vida Real (I) | UPValenciaX on edX | Course About Video[Video]. YouTube. https://www.youtube.com/watch?v=dP7-gXXXiaM&feature=youtu.be
Aporte personal:
La representación gráfica principal de los grafos es mediante la matriz de adyacencia, donde se usa filas y columnas para interpretar las conexiones entre los nodos del grafo, donde 1 es la conexión que tiene y 0 es porque no tiene arista con este nodo.
ACTIVDAD DE GRAFOS
PREGUNTAS:
Qué relación hay entre la estructura árbol y la estructura grafo? Puede ser un grafo un árbol?
Ambas estructuras de datos son dinámicas y su forma grafica son muy similares ya que el árbol tiene nodos y los grafos vértices, conectados o unidos donde se puede recorrer la estructura de diversas formas. Los grafos son, por así decirlo, un árbol general más avanzado, donde sus conexiones entre los puntos son más complejas y completas. Si un grafo puede ser un árbol, dependiendo de que tan grande es y su forma grafica, se puede identificar si es un grafo o árbol.
Es un grafo una estructura recursiva? Explique
Sí, ya que para recorrer llenar, recorrer y buscar en el grafo es necesario que halla recursividad.
Para qué tipo de problemas se utiliza la estructura grafo? De dos ejemplos
Los grafos son utilizados diariamente a la hora de tomar decisiones, resolver problemas o unir dos objetos. Los ejemplos más comunes en la utilización de un grafo es cuando queremos ir de un punto A a un punto B, el grafo analiza el recorrido, escogiendo la mejor y optima opción de ruta.
Otro ejemplo del uso de grafos, son las redes sociales, don se conecta millones de personas con el fin de transmitir información.
Como se puede representar la estructura grafo? Explique
Los grafos se pueden representar de dos formas:
Dinámica: se representa el grafo con dos estructuras, usando un vector que almacena los vértices y de allí, de cada posición del vector se conecta con una lista simplemente ligada que conectara con nodos que son los vértices que conecta el principal ubicado en el vector.
Estática: representa el grafo en matrices, donde la matriz de adyacencia consta de matriz cuadra de nxn, donde n son el numero de vértices del grafo, allí se representa que vértices están conectados, donde se plasma en la matriz con un 1 dicha conexión. La matriz de incidencia es una matriz nxm donde n son numero de vértices y m numero de aristas (conexiones), se enumeran las aristas y en la matriz se representa cada vértice con que aristas se conecta, llenándolo también con un 1 en la matriz.
Construya dos grafos: Uno dirigido y otro no dirigido