Taller - Grafos
Descargar el siguiente archivo y realizar el taller sobre grafos que en el se encuentra.
1. Para los siguientes grafos
Conteste las siguientes preguntas:
a.Explique la diferencia entre los dos grafos anteriores
Tipo de Grafo:
Grafo 1: Es un grafo no dirigido. Esto significa que las conexiones entre los nodos (representados por los círculos azules) no tienen una dirección específica. Es decir, si hay una conexión entre A y B, también existe una conexión de B a A.
Grafo 2: Es un grafo dirigido. En este caso, las conexiones tienen una dirección indicada por las flechas. Por ejemplo, hay una conexión de A a B, pero no existe una conexión de B a A.
Estructura:
Grafo 1: Tiene una estructura más simple, con dos grupos de nodos conectados entre sí.
Grafo 2: Presenta una estructura más compleja, con conexiones que forman un ciclo.
Conectividad:
Grafo 1: Todos los nodos están conectados entre sí, directamente o indirectamente.
Grafo 2: No todos los nodos están conectados entre sí. Por ejemplo, el nodo D solo tiene conexiones entrantes, pero no tiene conexiones salientes.
b. En el grafo dirigido hay una trayectoria para ir de D hasta A?. sí la hay describa la trayectoria y si no que le colocaría al grafo para que se de esa trayectoria y escríbala.
No existe una trayectoria directa para ir desde el vértice D hasta el vértice A. Esto se debe a que todas las aristas (las flechas) apuntan en dirección opuesta, es decir, desde un vértice con una letra más avanzada del alfabeto hacia uno con una letra menos avanzada.
Para que exista una trayectoria de D hacia A, necesitaríamos agregar al menos una arista que vaya desde D hacia A o hacia otro vértice que a su vez tenga una conexión directa o indirecta con A.
c. Diga cual es el número máximo de lados que pueden tener los dos grafos
Grafo 1:
Estructura: Este grafo parece estar incompleto. No se muestran todas las posibles conexiones entre los vértices.Posibles lados:Si consideramos que todas las conexiones son posibles (sin formar lazos, es decir, una arista que conecte un vértice consigo mismo), entonces el número máximo de lados dependería de la cantidad de vértices. Sin embargo, como la imagen no muestra todas las conexiones, no podemos dar un número exacto.
Grafo 2:
Estructura: Este grafo es un grafo dirigido. Las flechas indican la dirección de la conexión entre los vértices.Posibles lados: Al ser un grafo dirigido, cada par de vértices puede tener a lo sumo una arista que vaya de uno a otro.
Cálculo: Si tenemos n vértices, el número máximo de aristas dirigidas posibles es de n * (n-1). Sin embargo, en este grafo particular, hay conexiones que no se están utilizando (por ejemplo, no hay una arista directa de A a E). Por lo tanto, el número de lados actual es menor que el máximo teórico.
d. Represente el grafo dirigido con matriz de adyacencia
e. Represente el grafo no dirigido con lista ligada de adyacencia
f. Represente el grafo dirigido con matriz de incidencia
g. Represente el grafo dirigido con lista ligada de adyacencia
h. Cuantos ciclos se pueden dar en ambos gafos y escriba cada uno de ellos
Grafo 1
El primer grafo es un grafo no dirigido, es decir, las aristas no tienen una dirección específica.
Ciclos de longitud 3:
* A-C-B-A
* C-D-E-C
Ciclos de longitud 4:
* A-C-D-E-A
* A-C-E-D-A
* B-C-D-E-B
* B-C-E-D-B
No existen ciclos de mayor longitud ya que el grafo no tiene suficientes vértices conectados de forma adecuada.
Grafo 2
El segundo grafo es un grafo dirigido, lo que significa que las aristas tienen una dirección específica (indicada por las flechas).
Ciclos:
* A-B-D-A
* A-B-E-A
* B-C-E-B
i. Hallar el grado para cada uno de los vértices de cada grafo
Grafo 1
Vértice A: Tiene grado 2, ya que está conectado a los vértices B y C.Vértice B: También tiene grado 2, conectado a A y C.
Vértice C: Tiene grado 3, conectado a A, B y D.
Vértice D: Tiene grado 2, conectado a C y F.
Vértice E: Tiene grado 2, conectado a C y F.
Vértice F: Tiene grado 2, conectado a D y E.
Grafo 2
Vértice A: Tiene grado 2, conectado a B y D.Vértice B: Tiene grado 3, conectado a A, C y D.
Vértice C: Tiene grado 2, conectado a B y E.
Vértice D: Tiene grado 3, conectado a A, B y E.
Vértice E: Tiene grado 2, conectado a C y D.
2. Construir un algoritmo que permita crear la matriz de adyacencia en un grafo no dirigido.
3. Construir un algoritmo que permita crear la matriz de incidencia en un grafo no dirigido.
4. Defina con sus palabras:
a) Adyacencia
Se refiere a una relación entre los nodos (o vértices) de un grafo. Dos nodos se consideran adyacentes si están conectados directamente por una arista (o arco).
Grafos No Dirigidos: En un grafo no dirigido, si hay una arista que conecta dos vértices A y B, se dice que A y B son adyacentes.
Grafos Dirigidos: En un grafo dirigido, la adyacencia se determina según la dirección de las aristas. Un vértice A es adyacente a otro vértice B si existe una arista que va de A a B.
La relación de adyacencia se puede representar mediante una matriz de adyacencia o una lista de adyacencia, que son estructuras de datos utilizadas para almacenar la información de las conexiones entre los vértices en un grafo.
Lista de adyacencia _ AcademiaLab. (s. f.). https://academia-lab.com/enciclopedia/lista-de-adyacencia/
https://www.researchgate.net/figure/Figura-1-Representacion-de-un-grafo-con-su-matriz-de-adyacencia-MONSALVE-2008-Otra_fig1_273459038
b) Incidencia
Se refiere a la relación entre los vértices y las aristas de un grafo. Específicamente:
- Un vértice se dice que incide en una arista si la arista conecta a ese vértice con otro vértice.
- En términos formales, en un grafo no dirigido, para una arista que une dos vértices A y B (denotada como A, B, ambos vértices A y B inciden en esa arista.
Grafo No Dirigido: En este tipo de grafo, cada arista une dos vértices, y cada uno de esos vértices incide en la arista.
Grafo Dirigido: En un grafo dirigido, una arista tiene una dirección específica. Por ejemplo, si existe una arista que va de "A" a "B" (denotada como "A-B", se dice que el vértice "A" incide en la arista como el extremo de inicio, y "B" incide como el extremo de llegada.
https://www.unipamplona.edu.co/unipamplona/portalIG/home_23/recursos/general/11072012/grafo3.pdf
Platzi: Plataforma de aprendizaje profesional online. (s. f.). https://platzi.com/clases/1319-discretas/12226-matriz-de-incidencia/
c) Grado de un grafo
El grado de un vértice en un grafo es una medida que indica cuántas aristas están conectadas a ese vértice. Dependiendo del tipo de grafo, la definición puede variar ligeramente:
Grados en Grafos No Dirigidos:
- El grado de un vértice " V " se denota como "d(v)" y se define como el número de aristas que inciden en " V ".
- Por ejemplo, si un vértice "A" tiene tres aristas conectadas a él, entonces su grado es 3.
Grados en Grafos Dirigidos:
- En grafos dirigidos, se distingue entre:
- Grado de entrada "d - (V)": el número de aristas que llegan al vértice "V".
- Grado de salida "d +(V)": el número de aristas que salen desde el vértice "V".
- El grado total de un vértice en un grafo dirigido se obtiene sumando el grado de entrada y el grado de salida:
d(v) = d^-(v) + d^+(v)
Pozo, S. (s. f.). Estructuras de datos: Doblemente enlazadas. © 2000 Salvador Pozo. https://conclase.net/c/edd/cap5
Hor_Dan. (2017, 12 octubre). GoConqr - Grafos. GoConqr. https://www.goconqr.com/mapamental/2631374/grafos
d) Trayectoria
Es una secuencia de vértices en un grafo en la que cada par consecutivo de vértices está conectado por una arista. Formalmente, se puede definir como sigue:
- Dado un grafo G = (V, E) , donde V es el conjunto de vértices y E es el conjunto de aristas, una trayectoria es una secuencia finita de vértices (v1, v2, .... , vk ) tal que para cada i (donde 1 ≤ i < k), la arista (vi, vi + 1 ) pertenece a " E ".
Además, se pueden clasificar las trayectorias de acuerdo a ciertas características:
- Trayectoria simple: Una trayectoria en la que no se repite ningún vértice (excepto, potencialmente, el vértice inicial y final si es un ciclo).
-Trayectoria cerrada: Una trayectoria donde el primer y el último vértice son el mismo, formando un ciclo.
Torres, V. (2020, 4 mayo). GoConqr - Teoría de las gráficas. GoConqr. https://www.goconqr.com/mindmap/22531284/teoria-de-las-graficas
e ) Trayectoria simple
En un grafo es una secuencia de vértices conectados por aristas, donde cada vértice aparece solo una vez. En otras palabras, es un camino que recorre todos los vértices que toca sin repetir ninguno, excepto posiblemente el primero y el último (en el caso de un ciclo).
Elementos clave de una trayectoria simple:
- Secuencia de vértices: Un orden específico en el que se visitan los vértices.
- Aristas: Las conexiones entre los vértices en la secuencia.
- No repetición de vértices: Cada vértice aparece una única vez, excepto en el caso de un ciclo.
nipamplona.edu.co/unipamplona/portalIG/home_23/recursos/general/11072012/grafo3.pdf
https://www.researchgate.net/figure/A-simple-DAG-with-critical-path-highlighted_fig1_221257693
f) Ciclo
Un ciclo en un grafo es un camino que comienza y termina en el mismo vértice, sin repetir ningún otro vértice en el camino. Es como dar una vuelta completa por un circuito sin pasar dos veces por el mismo punto.
Elementos clave de un ciclo:
- Camino cerrado: El inicio y el final del camino coinciden.
- Sin repeticiones: Cada vértice del ciclo se visita una única vez, excepto el primero y el último (que son el mismo).
- Aristas: Las conexiones entre los vértices forman una secuencia continua.
GRAFOS II. (s. f.). https://slidetodoc.com/grafos-ii-caminos-longitud-de-un-camino-la/
https://www.codeo.app/problemas/0x53-encontrar-ciclos-en-un-grafo-dirigido
g) Grafo conectado
Es un grafo en el que existe un camino entre cualquier par de vértices. Esto significa que, para cualquier par de vértices " U " y " V "en el grafo, puedes encontrar una secuencia de aristas que te permita ir desde " U " hasta " V."
En el contexto de los grafos, se pueden distinguir dos tipos:
- Grafo no dirigido: Un grafo no dirigido es conectado si, para cualquier par de vértices, hay al menos un camino no dirigido que los conecta.
- Grafo dirigido: Un grafo dirigido es conexo (o fuertemente conexo) si, para cualquier par de vértices " U " y " V ", hay un camino dirigido de " U " a " V " y, además, hay un camino dirigido de " V " a " U ".
Si un grafo no dirigido tiene un componente donde no se puede alcanzar todos los vértices desde un punto dado, se considera no conectado. Para grafos dirigidos, si no existe una forma de llegar de un vértice a otro, el grafo también se considera no conectado.
Grafo conexo - Wikiwand. (s. f.). https://www.wikiwand.com/es/articles/Grafo_conexo
Grafo conexo - Wikiwand. (s. f.). https://www.wikiwand.com/es/articles/Grafo_conexo
h ). Grafo fuertemente conectado
Es un tipo de grafo dirigido en el que, para cada par de vértices " U " y " V ", existe un camino dirigido de " U " a " V " y también un camino dirigido de " V " a " U ". En otras palabras, desde cualquier vértice se puede alcanzar a cualquier otro vértice siguiendo las aristas y respetando su dirección.
Características :
- Cada vértice del grafo puede ser alcanzado desde cualquier otro vértice.
- Si se elimina cualquier arista, el grafo puede seguir siendo fuertemente conectado, pero no necesariamente.
Grafos — Introducción a Algoritmos y Estructuras de Datos. (s. f.). https://rramosp.github.io/introalgs.v1/content/NOTAS%2008%20-%20Grafos.html
De Investigación Educativa, E., & De Investigación Educativa, E. (2021, 1 junio). Teoría de grafos. TareaEducativa.com | Cientos de Tareas Educativas y Publicaciones de Estudio. https://www.tareaeducativa.com/teorias/teoria-de-grafos.html
5. Investigar los Recorridos sobre grafos:
La operación de recorrer una estructura de datos consiste en visitar (procesar) cada uno de los nodos a partir de uno dado. Así, para recorrer un árbol se parte del nodo raíz y según el orden se visitan todos los nodos. De igual forma, recorrer un grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. Hay dos formas de recorrer un grafo: recorrido en profundidad y recorrido en anchura. Si el conjunto de nodos marcados se trata como una cola, entonces el recorrido es en anchura; si se trata como una pila, el recorrido es en profundidad.
Tambien se puede decir que son técnicas para visitar los nodos de un grafo en un orden específico. Hay varios métodos de recorrido, pero los dos más comunes son el DFS (Depth-First Search, o búsqueda en profundidad) y el BFS (Breadth-First Search, o búsqueda en anchura). Estos recorridos son importantes para analizar las conexiones y la estructura de un grafo y tienen aplicaciones en la búsqueda de rutas, la detección de ciclos, la conectividad y otros problemas en grafos.
https://www.udb.edu.sv/udb_files/recursos_guias/informatica-ingenieria/programacion-iv/2019/ii/guia-9.pdf
promedia ufps. (2017, 27 septiembre). Recorridos sobre grafos:DFS -BFS [Vídeo]. YouTube. https://www.youtube.com/watch?v=P45bRlCTqHI
5.1 Investigar que el Recorrido DFS sobre grafos y un ejemplo
Este método es una forma básica de recorrer un grafo implementando recursividad. En este recorrido se basan los recorridos preorden y postorden para árboles binarios. Supóngase que una persona se encuentra en algún sistema de cuevas interconectadas, o en un laberinto, en una cierta intersección (o nodo), y que se le pide a esta persona que busque la salida, que se encuentra en un determinado nodo. En esta búsqueda se podrían emplear varias opciones. Una posibilidad que probablemente no se utilizase sería la búsqueda en amplitud. Intuitivamente, una estrategia que comienza en algún nodo de la cueva y que después visita todos y cada uno de los nodos adyacentes siguientes de la cueva, no parece demasiado prometedora.
Se invoca a recorrido_en_profundidad (s) para algún nodo inicial "s". Procedimiento recorrido_en_profundidad 1. Se marca y visita "s". 2. Para cada vecino "w" de "s" Si el vecino "w" no está marcado Se invoca a recorrido_en_profundidad (w). El recorrido en profundidad persigue el mismo objetivo que el recorrido en anchura: visitar todos los vértices del grafo alcanzables desde un vértice dado. La búsqueda en profundidad empieza por un vértice "V" del grafo "G"; "V" se marca como visitado. Después se recorre en profundidad cada vértice adyacente a "V" no visitado; así hasta que no haya más vértices adyacentes no visitados.
https://www.udb.edu.sv/udb_files/recursos_guias/informatica-ingenieria/programacion-iv/2019/ii/guia-9.pdf
Ejemplo:
Daniel 54BHP. (2020, 28 marzo). Recorriendo un Grafo empleando DFS [Vídeo]. YouTube. https://www.youtube.com/watch?v=CebzXLIz3oo
5.2 Investigar que el Recorrido BFS sobre grafos y un ejemplo
El recorrido de búsqueda en anchura, en amplitud o expansión, es una estrategia aplicable indistintamente al caso de grafos dirigidos y no dirigidos. El recorrido en anchura es una generalización del recorrido por niveles de un árbol. Se trata de visitar un nodo inicial y luego a todos los nodos que están a un arco de distancia de éste, luego a todos los nodos que están a dos arcos de distancia de éste y así sucesivamente, hasta alcanzar a todos los nodos a los que se pueda llegar desde el nodo inicial. Una aplicación típica de este recorrido es la resolución de problemas de planificación. La búsqueda en amplitud se puede utilizar para hallar la distancia más corta entre algún nodo inicial y los nodos restantes del grafo. Esta distancia más corta es el mínimo número de aristas que hay que recorrer para pasar desde el nodo inicial hasta el nodo concreto que se esté examinando.
Comenzando en el nodo "s", esta distancia se calcula examinando todas las aristas incidentes en el nodo "s", y pasando después a un nodo adyacente "w", repitiéndose entonces todo el proceso. El recorrido continúa hasta que se hayan examinado todos los nodos del grafo. En una búsqueda en amplitud, cada nodo se visita o es procesado en algún sentido, dependiendo de la aplicación concreta. La búsqueda comienza en un nodo concreto del grafo. A continuación la búsqueda se extiende a los nodos del grafo que estén más próximos al nodo inicial antes de visitar ningún otro. Estos nodos están relacionados de alguna forma con el nodo especificado, y forman parte de un grupo que depende de la aplicación concreta. Inicialmente, se visitan todos aquellos nodos que sean adyacentes al nodo inicial. A continuación se visitan todos los nodos que estén a una distancia "2" del nodo inicial. Este proceso se repite hasta que se haya visitado todos los nodos posibles.
https://www.udb.edu.sv/udb_files/recursos_guias/informatica-ingenieria/programacion-iv/2019/ii/guia-9.pdf
Ejemplo:
Daniel 54BHP. (2020a, marzo 28). Recorriendo un Grafo empleando BFS [Vídeo]. YouTube. https://www.youtube.com/watch?v=J455oum16eU