1. Unidad I: Grafos y digrafos. Definiciones y ejemplos. Caminos y ciclos. Distancia entre dos vértices y diámetro de un grafo. Subgrafos. Grafos conexos. Grafos acíclicos. Árboles. Árboles enraizados: definición recursiva. Representación de grafos mediante matrices de adyacencia, matrices de incidencia y listas de adyacencia. Complejidad en tiempo de un algoritmo: peor caso y caso promedio. Notación O grande.
2. Unidad II: Recorrido de grafos y digrafos: primero en profundidad y primero en amplitud. Distancias más cortas de un vértice a todos los demás. Algoritmo de Dijkstra. Distancias más cortas entre todos los vértices. Algoritmo de Floyd. Clausura transitiva: Algoritmo de Warshall. Aplicaciones de la búsqueda en profundidad en digrafos: prueba de aciclicidad, clasificación topológica y determinación de las componentes fuertemente conexas.
3. Unidad III: Componentes conexas. Puntos de articulación. Componentes biconexas. Árboles de extensión de costo mínimo. Algoritmo de Prim. Algoritmo de Kruskal.
4. Unidad IV: Redes de flujo. Cortes: flujo neto y capacidad. Flujo máximo: método de Ford-Fulkerson. Algoritmo de Edmonds-Karp. Aplicación: Pareos máximos en grafos bipartitos.

Bibliografía

• Aho, A., Hopcroft, J D., Ullman, J. E. Algoritmos y Estructuras de Datos, Addison Wesley Iberoamericana, 1988.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms, 2nd ed., MIT Press, 2001.
• Reingold, E. M., Nievergelt, J., Deo, N. Combinatorial Algorithms, Prentice Hall, 1977.
• Sedgewick, R. Algorithms, Addison Wesley 1983.