Buenas estudiantes,
En la segunda clase vimos los conceptos de cubrimiento de vértices y de emparejamiento de aristas.
Enunciamos el Teorema de Konig, que establece que en todo grafo bipartito se cumple que el tamaño de cualquier cubrimiento de vértices de mínimo cardinal es igual al tamaño de cualquier emparejamiento máximo.
Vimos una prueba del Teorema de Konig utilizando el teorema fuerte de dualidad en programación lineal.
Un elemento central fue la integralidad de problemas de programación lineal entera y el hecho que las matrices de incidencia de grafos bipartitos son totalmente unimodulares, lo que quedó como ejercicio.
En la clase que sigue enunciaremos 5 problemas de optimización combinatoria y definiremos el concepto de algoritmo de aproximación.
¡Que sigan disfrutando del curso!
Cordiales saludos,
Pablo.