Docentes: Gabriela Argiroffo, Patricia Dobson, Valeria Leoni, Pablo Torres.

Comienzo: Viernes 18/03/2016. Horarios: Viernes de 9:00 hrs a 13:00 hrs. Aula 34 (tercer piso, final del pasillo paralelo a Pellegrini).

Prácticas y apuntes.

Contenidos:

Unidad 1
Clases de grafos:

Grafos perfectos, de comparabilidad y cordales. Subclases de grafos cordales: UV, DV, RDV, de intervalos. Clases hereditarias. Clases F-free. Clases de grafos a partir de operaciones.

Unidad 2
Conectividad y caminos:

Cortes y Conectividad, Arista-Conectividad, Conectividad en Digrafos, k-conectividad y k-arista conectividad. Teorema de Menger. Redes y Flujos. Flujos enteros. Aplicaciones.

Unidad 3
Coloreo de grafos:

Coloreo clásico por vértices, Teorema de Brook, Coloreo clásico por aristas, Teorema de Vizing. Aplicaciones y algorítmos. Coloreos y productos de grafos. Variantes de coloreo: Coloreo por listas, k-upla coloreo. Coloreos y homomorfismos de grafos. Coloreos en clases particulares de grafos.

Unidad 4
Matching y factores:

Matching Máximo, Teoremas Min-Max, Conjuntos Independientes y Coberturas. Conjuntos Dominantes. Algoritmos y aplicaciones, Matching máximo en grafos bipartidos, Matching estables. Teorema de Tutte, f-factores de grafos en general, Algoritmo de Edmonds y Karp.

Unidad 5
Planaridad:

Inmersiones planas. Grafos duales. Caracterización de grafos planares. Teorema de Kuratowski.