Taller: Introducción a la Teoría de Grafos

Universidad Tecnológica de Pereria

1. Introduccion y Definicion de terminos -> 30min

   • Que es un grafo
   • Que es un nodo, una arista
   • Grafos dirigidos y no dirigidos
   • Representacion en memoria de un grafo (Matriz de Adyacencia y Listas de Adyacencia)

2. Busqueda Primero en Anchura -> 30min

   • Definicion formal
   • Implementacion algoritmo
   • Aplicaciones
     • Laberinto (Single Source Shortest Path Unweighted Graph)
     • Binary Land (Single Source Shortest Path Unweighted Graph)
     • Minimo numero de operaciones (Single Source Shortest Path Unweighted Graph)

3. Busqueda Primero en Profundidad -> 30min

   • Definicion formal
   • Implementacion algoritmo
   • Aplicaciones
     • Bote de Pintura (Flood Fill)
     • Pensum (Topological Sort)

4. Breve explicacion de las Componentes Fuertemente Conexas (Strongly Connected Components) -> 30min

   • Definición formal
   • Aplicaciones en Redes sociales