ACTIVIDAD 7-GRAFOS

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?

Respuestas:

1. Los grafos son estructuras discretas que constan de vértices y aristas que conectan entre si esos vértices. Por lo tanto un grafo G costa de dos partes: 1) Un conjunto V = V (G) cuyos elementos se denominan vértices, puntos o nodos de G. 2) Un conjunto E = E(G) de pares de vértices distintos denominados aristas de G.

 2. Los grafos contienen nodos, bordes y propiedades que se utilizan para representar y almacenar datos de una forma que no permiten las bases de datos relacionales.

3. Los grafos se pueden clasificar en diferentes tipos dependiendo de cómo se defina la relación entre los elementos: podemos encontrar grafos dirigidos o no dirigidos y etiquetados o no etiquetados. También se pueden combinar ambas categorías.

4. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

Ejercicios Realizados Lista Ligada, Matriz de Adyacencia y Incidencia 

Recorridos de Grafos

Recorrido DFS 0 Búsqueda en Profundidad

Un Recorrido en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo. Es una generalización del recorrido preorden de un árbol.

La estrategia consiste en partir de un vértice determinado v y a partir de alli, cuando se visita un nuevo vértice, explorar cada camino que salga de él. Hasta que no se haya finalizado de explorar uno de los caminos no se comienza con el siguiente. Un camino deja de explorarse cuando se llega a un vértice ya visitado.

Si existían vértices no alcanzables desde v el recorrido queda incompleto; entonces, se debe seleccionar algún vértice como nuevo vértice de partida, y repetir el proceso.

Presentación para los recorridos en los grafos

Ejercicio Practico en clase de reccorido grafos DFS

Estudiantes: PAUL ANDRÉS FURNIELES MEZA  Y BREYNER YULIAN BECERRA TABA