Clase 6. Representaciones de grafos y recorridos¶
Viernes 11 de septiembre de 2026.
Las cuatro formas de guardar un grafo y cómo se construye cada una, con lo que ocupa y lo que cuesta consultarla. De ahí sale cuál conviene, y de ahí la pregunta que viene después: cómo se recorre un grafo, en profundidad y en amplitud.
-
Representaciones y recorridos
Las cuatro formas de guardar un grafo con su costo, los dos recorridos en pseudocódigo y en Python, y por qué ambos cuestan \(\Theta(V+E)\) sobre listas y \(\Theta(V^2)\) sobre matriz.
-
Repaso de grafos
Definiciones, los cinco tipos, terminología, el teorema del apretón de manos, las familias, topologías, subgrafos y complementos.
Ejercicios¶
Siete interactivos, uno por cada tema de la sesión y en el mismo orden en que se dieron: construir las representaciones, comparar el costo de una consulta sobre las tres, ver qué pasa sin la marca de visitados, los dos recorridos paso a paso, el costo con controles y los cuatro errores que más cuestan. Después, diez para resolver en papel, incluido un problema de juez.
Todos están en la página de ejercicios.
Antes de entrar¶
Conviene tener a mano las definiciones y familias de grafos, que son la base de todo lo que sigue.