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.


Bibliografía

  1. C. Berge. Graphs and hypergraphs. North-Holland Publishing, Amsterdam, edición revisada, 1976.

  2. J. A. Bondy y U. S. R. Murty. Graph theory, volumen 244 de Graduate Texts in Mathematics. Springer, New York, 2008.

  3. R. Diestel. Graph theory, volumen 173 de Graduate Texts in Mathematics. Springer, Heidelberg, cuarta edición, 2010.

  4. M. C. Golumbic. Algorithmic graph theory and perfect graphs, volumen 57 de Annals of Discrete Mathematics, Elsevier, Amsterdam, segunda edición, 2004.

  5. F. Harary. Graph theory. Addison-Wesley, Reading, MA, 1969.

  6. D. B. West. Introduction to graph theory. Prentice Hall, Upper Saddle River, NJ, 2001.