Matemática discreta

Cursada sugerida

Segundo cuatrimestre del segundo año, en paralelo con el curso “Algoritmos y estructuras de datos II”.

Objetivos

Conocer las definiciones, problemas y algoritmos básicos sobre grafos y redes.

Correlatividades

Para cursar y aprobar el curso es necesario tener aprobado el curso “Lógica y teoría de números”.

Contenidos mínimos

• Teoría de grafos. Adyacencia, grado de un vérctice, isomorfismos, caminos, conexión, etc. Grafos bipartitos. Árboles: caracterización, árbol generador. Grafos Eulerianos y Hamiltonianos.Coloreo de grafos y número cromático de un grafo. Conjunto independiente y número de estabilidad de un grafo. 

• Algoritmos sobre grafos. Recorridos de grafos: BFS y DFS. Algoritmos para detección de circuitos en grafos. 

• Redes. Definiciones y propiedades. Algoritmos para encontrar el camino mínimo en un grafo: Algoritmo de Dijkstra, Algoritmo de Ford. Algoritmos para encontrar el flujo máximo en una red: Algoritmo de caminos aumentantes y algoritmo de Warshall.

Carga horaria

Una clase teórica semanal y una clase práctica semanal, una clase es de 4 horas y la otra es de 2 horas cada una durante 16 semanas, totalizando 96 horas de clase.

Régimen de aprobación

Para aprobar el curso, se deben aprobar dos exámenes parciales o sus respectivos recuperatorios. El primer examen parcial se toma hacia la mitad de la cursada y el segundo al final de la cursada.