3.3.2 DMC/Teoría de Grafos

Estructura y propiedades de grafos: conectividad, coloraciones, emparejamientos, planaridad y teoría espectral de grafos.
Temas:
Core

• Grafos: definiciones, isomorfismo, sucesiones de grados, árboles y árboles generadores
• Conectividad, teorema de Menger y flujos en redes (flujo máximo-corte mínimo)
• Emparejamientos (teorema de Hall), coloraciones de grafos y el polinomio cromático
• Grafos planares, fórmula de Euler, teorema de Kuratowski y el teorema de los cuatro colores
• Matrices de adyacencia y laplaciana, valores propios y grafos expandidores

Aprendizaje esperado (Learning Outcomes):
Core:

1. Identificar propiedades estructurales de grafos (conectividad, planaridad, bipartitud) y aplicar la fórmula de Euler [Familiarizarse]
2. Aplicar el teorema de matrimonio de Hall y algoritmos de flujo en redes a problemas de emparejamiento y enrutamiento [Usar]
3. Analizar el espectro de un grafo para acotar su número cromático y sus propiedades de conectividad [Evaluar]