Download Matemáticas discretas

Temario del curso básico de matemáticas discretas
I Topología combinatoria
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Gráficas. Matriz de incidencia. Espectro de una gráfica
Árboles. Árbol generador. Circuitos y cortes
Gráficas planares. Teorema de Euler
Apareamientos perfectos y factorización
Caminos Eulerianos y Hamiltonianos
Coloraciones de gráficas. Polinomio cromático
Polinomio de Tutte. Contracción y borrado. Menores
Automorfismos de gráficas. Gráficas de Cayley. Gráficas fuertemente regulares
Representación topológica de gráficas. Encajes en superficies. Encajes en R3. Gráficas de
Kuratowski. Género y dualidad
Complejos simpliciales. Triangulaciones. Encajes celulares. Algoritmos de encaje
II Álgebra combinatoria
1.
2.
3.
Técnicas de conteo. Coeficientes elementales de conteo. Número de subespacios de un espacio
vectorial. Particiones. Recursión e inversión. Números de Stirling. Funciones generadoras
Diagramas de Ferrer. Sucesiones unimodales. Involuciones
Conjuntos parcialmente ordenados. Latices. Inversión de Möbius. Álgebra de incidencia
III Optimización combinatoria
1.
2.
3.
4.
5.
6.
7.
Desigualdades lineales. Introducción a conos, poliedros y politopos. Lema de Farkas. Teorema
Caratheodory
Programación lineal básica. Dualidad
Digráficas. Redes y flujos. Teorema de Máx-Mín. Algoritmos
Estructura de poliedros. Facetas, caras y vértices. Descomposición. Poliedro de apareamientos.
Poliedro de cortes
Programación entera básica
Unimodularidad y optimización
Complejidad computacional
Referencias
Aigner, M.
Archideacon, D.
Biggs, N.
Bondy, J.A., Murty, U.S.R.
Gross, J., Tucker, T.
Johnson, D.
Lovaz, L., Plummer, M.
Newhauser, G.
Oxley, J.
Schrijver, A.
Stanley, R.
van Lint, J.H., Wilson R.M.
Welsh, D.
Ziegler, G.
Combinatorial theory
Topological graph theory
Discrete mathematics
Graph theory with applications
Topological graph theory
Computers and intractability
Matching theory
Integer and combinatorial optimization
Matroid theory
Theory of linear and integer programming
Enumerative combinatorics
A course in combinatorics
Complexity: knots, colorings and counting
Lectures on polytopes
1