NOMBRE DE LA MATERIA: MT361 COMBINATORIA
DEPARTAMENTO DE ADSCRIPCION: DEPARTAMENTO DE MATEMATICAS
CARGA HORARIA SEMESTRAL: TEORIA: 100 PRACTICA: 0
CREDITOS: 13
TIPO: CURSO
AREA DE FORMACION: OPTATIVA
PREREQUISITOS: MT260 MATEMATICAS DISCRETAS

OBJETIVO GENERAL:

OBJETIVOS ESPECIFICOS:

CONTENIDO:
1.-Topología Combinatoria
1.1 Gráficas. Matriz de incidencia. Espectro de una gráfica
1.2 Arboles. Arbol generador. Circuitos y cortes
1.3 Gráficas planares. Teorema de Euler
1.4 Apareamientos perfectos y factorización
1.5 Caminos Eulerianos y Hamiltonianos
1.6 Coloraciones de gráficas. Polinomio cromático
1.7 Polinomio de Tutte. Contracción y borrado. Menores
1.8 Automorfismos de gráficas. Gráficas de Cayley. Gráficas fuertemente regulares.
1.9 Representación topológica de gráficas. Encajes en superficies. Encajes en R3. Gráficas de Kuratowski. Género y dualidad
1.10 Complejos simpliciales. Triangulaciones. Encajes celulares. Algoritmos de encaje.
2. Algebra Combinatoria
2.1 Técnicas de conteo. Coeficientes elementales de conteo. Número de subespacios de un espacio vectorial. Particiones. Recursión e inversión.
2.2 Números de Stirling. Funciones generadoras
2.3 Diagramas de Ferrer. Sucesiones unimodales. Involuciones
2.4 Conjuntos parcialmente ordenados. Latices. Inversión de Möbius. Algebra de incidencia
3. Optimización Combinatoria
3.1 Desigualdades lineales. Introducción a Conos, poliedros y politopos.
3.2 Lema de Farkas. Teorama de Caratheodory.
3.3 Programación lineal básica. Dualidad
3.4 Digráficas. Redes y flujos. Teorema de Máx-Mín. Algoritmos
3.5 Estructura de poliedros. Facetas, caras y vértices. Descomposición.
3.6 Poliedro de apareamientos. Poliedro de cortes.
3.7 Programación entera básica
3.8 Unimodularidad y optimización
3.9 Complejidad computacional  
BIBLIOGRAFIA BASICA
Gross J., Tucker T. Topological graph theory
Archideacon D. Topological graph theory
Lovaz L., Plummer M. Matching theory
Bondy J.A., Murty U.S.R. Graph theory with applications
Aigner M. Combinatorial theory
Oxley J. Matroid theory
Stanley R. Enumerative combinatorics
Biggs, N. Discrete mathematics
van Lint J.H., Wilson R.M. A course in combinatorics
Schrijver A. Theory of linear and integer programming
Ziegler, G. Lectures on polytopes
Newhauser G. Integer and combinatorial optimization
Welsh D. Complexity: knots, colorings and counting
Johnson D. Computers and intractability