Algoritmos en teoría de gráficas#

Introducción#

En esta parte del texto discutimos varios de los algoritmos más importantes de teoría de gráficas. Para ello, utilizamos la teoría y herramientas desarrolladas en las partes anteriores. La teoría de gráficas da lugar a muchas preguntas algorítmicas naturales. Las heurísticas que hemos discutido nos ayudan a resolver muchas de ellas. Hacia el final del texto, hablaremos de los problemas que no se sabe cómo resolver rápidamente.

Temario#

  • Implementaciones de gráficas y variantes

  • Uso básico de NetworkX

  • Búsqueda por anchura

  • Aplicaciones de búsqueda por anchura

  • Búsqueda por profundidad

  • Aplicaciones de búsqueda por profundidad

  • Árboles de peso mínimo: algoritmos de Prim y Kruskal

  • Caminos de peso mínimo: algoritmos de Dijkstra y Floyd-Warshall

  • Redes, flujos y flujos máximos

  • Algoritmo de Ford-Fulkerson y Edmonds-Karp

  • Reducciones algorítmicas y clases P, NP y NP-completo

  • Problemas de gráficas NP-completos