Teoría de Grafos y Complejidad

Acerca de este curso

Teoría de Grafos y Complejidad estudia las redes, sus propiedades estructurales y los algoritmos que permiten resolver problemas fundamentales, junto con la clasificación de su dificultad computacional. El curso recorre desde los conceptos básicos de grafos y algoritmos clásicos hasta la ubicación de problemas en las clases de complejidad P, NP y NP-completo.

Las lecciones son breves y autocontenidas, diseñadas para el formato en vídeo y el estudio guiado, con progreso claro. El objetivo es una base sólida en grafos y complejidad que prepare al estudiante para asignaturas de informática teórica, optimización y algoritmos avanzados.

Modelar problemas reales mediante grafos y analizar sus propiedades estructurales.
Aplicar algoritmos clásicos de grafos: recorridos, árboles generadores, caminos mínimos y flujos.
Entender conceptos clave de conectividad, planaridad, coloreado, emparejamientos y cubrimientos.
Construir y analizar conteos combinatorios en grafos (polinomio cromático, árboles, emparejamientos).
Comprender fundamentos de complejidad computacional y las clases P, NP y NP-completo.
Identificar la dificultad de problemas clásicos de grafos y distinguir los que son resolubles en P de los NP-completos.

Contenido del curso

Módulo 1: Fundamentos de teoría de grafos
Terminología básica y representaciones clave.

Lección 1.1: Definiciones y terminología (tipo de grafos)
Lección 1.2: Representaciones: listas, matrices, ventajas/desventajas
Lección 1.3: Secuencias gráficas y el algoritmo Havel–Hakimi
Lección 1.4: Operaciones sobre grafos: complementos, unión, intersección
Lección 1.5: Modelado de problemas reales como grafos

Módulo 2: Conectividad, recorridos y distancias
Descubre la estructura global a través de conectividad y caminos.

Acerca de este curso

¿Qué aprenderás?

Contenido del curso

Módulo 1: Fundamentos de teoría de grafos Terminología básica y representaciones clave.

Lección 1.1: Definiciones y terminología (tipo de grafos)

Lección 1.2: Representaciones: listas, matrices, ventajas/desventajas

Lección 1.3: Secuencias gráficas y el algoritmo Havel–Hakimi

Lección 1.4: Operaciones sobre grafos: complementos, unión, intersección

Lección 1.5: Modelado de problemas reales como grafos

Módulo 2: Conectividad, recorridos y distancias Descubre la estructura global a través de conectividad y caminos.

Lección 2.1: Componentes conexas, DFS y BFS

Lección 2.2: Caminos simples, ciclos, cierre transitivo

Lección 2.3: Distancia, diámetro, excentricidad

Lección 2.4: Conectividad k y vulnerabilidad (vértices y aristas)

Lección 2.5: Aplicaciones: redundancia y robustez

Módulo 3: Árboles y bosques Grafos acíclicos y sus propiedades estructurales.

Lección 3.1: Definiciones y propiedades equivalentes

Lección 3.2: Recorridos: pre, in, post, BFS y DFS en árboles

Lección 3.3: Codificación de árboles: Prüfer y otras codificaciones

Lección 3.4: Algoritmos de árboles generadores mínimos (Prim y Kruskal)

Lección 3.5: Aplicaciones: redes, hierarquías, backbones

Módulo 4: Euler, Hamilton y planaridad Clásicos de grafos con implicaciones profundas.

Lección 4.1: Grafos Eulerianos y semieulerianos

Lección 4.2: Caminos Hamiltonianos: definición y heurísticas

Lección 4.3: Grafos planares: criterios y teoremas de Kuratowski y Euler

Lección 4.4: Grafos duales y planaridad en la práctica

Lección 4.5: Aplicaciones: circuitos, rutas, mapas

Módulo 5: Coloreado y particiones estructurales Asignación de recursos y particiones estratégicas.

Lección 5.1: Número cromático y cota superior (greedy coloring)

Lección 5.2: Coloreo de aristas y teorema de Vizing (visión)

Lección 5.3: Cliques, conjuntos independientes, y cubrimientos

Lección 5.4: Teoremas de Turán y Ramsey (visión conceptual)

Lección 5.5: Aplicaciones: horarios, frecuencia, planificación

Módulo 6: Emparejamientos y cubrimientos Modelos de asignación optimizada en estructuras bipartitas.

Lección 6.1: Teorema de Hall y emparejamientos en bipartitos

Lección 6.2: Algoritmo de Kuhn y búsqueda de emparejamientos máximos

Lección 6.3: Cubrimientos mínimos y su dualidad con emparejamientos

Lección 6.4: Extensiones y perspectiva general en no bipartitos

Módulo 7: Flujos en redes Transporte eficiente en redes dirigidas.

Lección 7.1: Definición de flujo y corte; modelo matemático

Lección 7.2: Algoritmo de Ford–Fulkerson

Lección 7.3: Edmonds–Karp: mejora y complejidad

Lección 7.4: Teorema de flujo máximo – corte mínimo y aplicaciones

Módulo 8: Algoritmos sobre grafos y análisis de complejidad Resolver y evaluar problemas clásicos sobre grafos.

Lección 8.1: Caminos mínimos: Dijkstra y Bellman–Ford

Lección 8.2: Ordenación topológica y aplicaciones en DAGs

Lección 8.3: Componentes fuertemente conexas: Kosaraju/Tarjan

Lección 8.4: Evaluación de coste: notación asintótica y madejo práctico

Lección 8.5: Ejemplos en problemas reales: dependencia, scheduling

Módulo 9: Combinatoria en grafos y conteo exacto Construir conteos en estructuras complejas.

Lección 9.1: Inclusión–exclusión aplicado a subgrafos

Lección 9.2: Polinomio cromático: concepto e interpretación

Lección 9.3: Conteo de árboles: Kirchhoff (visión general)

Lección 9.4: Esquemas aproximados de conteo y su necesidad

Módulo 10: Complejidad computacional — fundamentos Clases básicas para problemas de decisión y algoritmo.

Lección 10.1: Modelos de cómputo y notación O, Ω, Θ

Lección 10.2: Clases P, NP y problemas de decisión vs optimización

Lección 10.3: Reducciones polinomiales y noción de NP-completo

Lección 10.4: SAT y 3SAT como problemas pivotales en NP

Módulo 11: Complejidad en grafos Ubicar problemas clásicos de grafos en el mapa de complejidad.

Lección 11.1: Clique, Independiente y Cobertura mínima (NP-completos)

Lección 11.2: Hamiltonian Path/Cycle y TSP (decisión)

Lección 11.3: Coloración de grafos (problema NP-completo)

Lección 11.4: Cortes máximos y problemas en P; contraste

Resources

Módulo 1: Fundamentos de teoría de grafos
Terminología básica y representaciones clave.

Módulo 2: Conectividad, recorridos y distancias
Descubre la estructura global a través de conectividad y caminos.

Módulo 3: Árboles y bosques
Grafos acíclicos y sus propiedades estructurales.

Módulo 4: Euler, Hamilton y planaridad
Clásicos de grafos con implicaciones profundas.

Módulo 5: Coloreado y particiones estructurales
Asignación de recursos y particiones estratégicas.

Módulo 6: Emparejamientos y cubrimientos
Modelos de asignación optimizada en estructuras bipartitas.

Módulo 7: Flujos en redes
Transporte eficiente en redes dirigidas.

Módulo 8: Algoritmos sobre grafos y análisis de complejidad
Resolver y evaluar problemas clásicos sobre grafos.

Módulo 9: Combinatoria en grafos y conteo exacto
Construir conteos en estructuras complejas.

Módulo 10: Complejidad computacional — fundamentos
Clases básicas para problemas de decisión y algoritmo.

Módulo 11: Complejidad en grafos
Ubicar problemas clásicos de grafos en el mapa de complejidad.