Programa
Unidad I: Nociones básicas. Grafos. Matrices de incidencia y adyacencia. Isomorfismo. Grafos especiales. Caminos y ciclos. Grafos bipartitos. Grafos sin triángulos. Sucesiones gráficas. Circuitos eulerianos en grafos. Digrafos y orientación. Digrafos eulerianos. Número de circuitos eulerianos en digrafos. Etiquetados elegantes (graceful labelings).
Unidad II: Árboles generadores y distancia: Árboles. Caracterizaciones. Árboles generadores y su enumeración. Fórmula de Cayley. Códigos de Prüfer. Teorema de Kirchhoff. Teorema de Tutte. Algoritmos de Kruskal y Prim. Implementación. Estructura de datos para conjuntos disjuntos. Algoritmo de Dijkstra. Análisis de complejidad.
Unidad III: Matchings. Definiciones. Matching máximos. Teorema de Berge. Teorema de Hall. Cubrimiento por vértices. Teorema de König. Teorema de Gallai. Dominación. Conjuntos independientes dominantes. Algoritmo de camino aumentante. Matchings estables. Algoritmo de Galey y Shapley. Matching máximo (pesado) en grafos bipartitos. El algoritmo húngaro de Kuhn-Munkres. Algoritmo de Hopcroft y Karp. Análisis de complejidad.
Unidad IV: Conectividad y flujo. Conectividad. Vértices y aristas de corte. Grafos de Harary. Conectividad por aristas. Descomposición en bloques. k-conectividad. Grafos 2-conexos y descomposición en orejas. Grafos 2-arista-conexos y descomposición en orejas cerradas. Teorema de Menger. Flujo en redes. Dualidad. Teorema de flujo máximo y corte mínimo. Flujos enteros. Algoritmo de Ford-Fulkerson. Algoritmo de Edmonds y Karp. Análisis de complejidad.
Unidad V: Planaridad. Grafos planares y no planares. Grafos planares exteriores. Grafo dual. Grafos bipartitos planares. Grafos planares maximales. Fórmula de Euler. Poliedros regulares. Caracterización de los grafos planares. Teorema de Kuratowski y su demostración. Coloreo de grafos planares.
- C. Berge. Graphs and hypergraphs. North-Holland Publishing, Amsterdam, edición revisada, 1976.
- J. A. Bondy y U. S. R. Murty. Graph theory, volumen 244 de Graduate Texts in Mathematics. Springer, New York, 2008.
- R. Diestel. Graph theory, volumen 173 de Graduate Texts in Mathematics. Springer, Heidelberg, cuarta edición, 2010.
- M. C. Golumbic. Algorithmic graph theory and perfect graphs, volumen 57 de Annals of Discrete Mathematics, Elsevier, Amsterdam, segunda edición, 2004.
- F. Harary. Graph theory. Addison-Wesley, Reading, MA, 1969.
- D. B. West. Introduction to graph theory. Prentice Hall, Upper Saddle River, NJ, 2001.