Material de la asignatura

• Tema 1. Introducción. Nociones básicas
• Tema 2. Árboles
  • Nociones generales. Árboles de búsqueda
  • Árboles generadores óptimos
  • Árboles de decisión
• Tema 3. Caminos y distancias
• Tema 4. Complejidad de algoritmos (tema transversal)
  • Complejidad (I)
  • Complejidad (II). Problemas NP-completos
• Tema 5. Conectividad y orientabilidad
• Tema 6. Flujos en redes. Emparejamientos y recubrimientos.
  • Flujos
  • Emparejamientos y recubrimientos
  • Algoritmos aproximados para “Vertex cover problem”
• Tema 7. Recorridos en grafos.
  • Recorridos eulerianos.
  • Caminos hamiltonianos. “Problema del Viajante (TSP)”
• Tema 8. Planaridad
• Tema 9. Coloración.
  • Número cromático. Independencia. Algoritmos para colorear
  • Teorema de los cuatro colores
• Tema 10. Funciones generatrices.
  • Funciones generatrices ordinarias. Números de Catalan
  • Funciones generatrices exponenciales
  • Particiones

Enlaces y software sobre grafos

• Sofware para visualizar algoritmos en grafos. Desarrollado por alumnos de la UPM
• Enlaces interesantes sobre grafos