Matemática Discreta II - 2023

Repositorio que contiene apuntes, algoritmos y el proyecto final de la materia Matemática Discreta II de la Licenciatura en Ciencias de la Computación de la Facultad de Matemática, Astronomía, Física y Computación de la Universidad Nacional de Córdoba.

Proyecto

El proyecto realizado con Juan Bratti puede encontrarse en el siguiente repositorio.

Algoritmos

Durante el desarrollo de la cursada he implementado los algoritmos que se han visto en clase, con el objetivo de corroborar todos los pasos (principalmente en flujo), comparando con el output de los programas. Por ello mismo, considero que son de gran utilidad para ahorrar mucho tiempo a la hora de hacer las guías.

Algoritmo	Descripción	Código
Coloreo greedy	Dado un orden	CPP
Coloreo greedy general	Brute $n!$ (da $\chi(G)$ )	CPP
Flujo greedy		CPP
Flujo Ford-Fulkerson		CPP
Flujo Edmonds-Karp		CPP
Flujo Dinic		CPP
Matching sin pesos		CPP
Matching Gross	Minimizar mayor costo	CPP
Matching Húngaro	Minimizar suma	CPP

Resúmenes

Tema	Resumen
Generalidades de grafos	MD
Coloreo	MD
Flujo	MD
Matchings	MD
Códigos de Corrección de Errores	MD

Demostraciones para el Final

La lista de demostraciones que nos tomaron en el final se puede encontrar aquí. A continuación, se presentan las demostraciones desarrolladas:

Demostración	Resolución
Complejidad de Edmonds-Karp	PDF
Las distancias de EK no disminuyen en pasos sucesivos	PDF
Complejidad de Dinic	PDF
Teorema MFMC	PDF
2-COLOR es polinomial	PDF
Teorema de Hall	PDF
Teorema de König	PDF
Coloreo de aristas en bipartito	PDF
Complejidad de Húngaro	PDF
Teorema de la cota de Hamming	PDF
Propiedad de la matriz de chequeo H	PDF
Teorema del polinomio generador	PDF