Saltar a contenido

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.

    Entrar

  • Repaso de grafos


    Definiciones, los cinco tipos, terminología, el teorema del apretón de manos, las familias, topologías, subgrafos y complementos.

    Diapositivas

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.