Combinatoria y teoría de grafos

Instructor: Rafael S. González D'León
Email: rafael.gonzalezl@usa.edu.co
Página web: http://dleon.combinatoria.co
Horas de oficina: Lunes 2:00 pm a 3:00 pm o por cita.

Clases

Lunes y Martes 4:00-6:00 pm.

Literatura

A First Course in Discrete Mathematics. Ian Anderson.
Notas de clase ( en PDF).

Contenido del curso

La combinatoria es la rama de la matemática que se encarga de la enumeración y estructura de familias de objetos discretos. Un grafo es un objeto discreto formado por un conjunto de nodos y un conjunto de aristas entre ellos. La teoría de grafos se encarga entonces de la enumeración y el estudio de las propiedades estructurales de familias de grafos. Este es principalmente un curso introductorio a la teoría de enumeración combinatoria en donde usaremos la teoría de grafos como campo de juego en donde usar herramientas combinatorias. Desde el punto de vista enumerativo se cubrirán los principios básicos de conteo; permutaciones y números factoriales; subconjuntos y coeficientes binomiales; composiciones y composiciones débiles; particiones de conjuntos y números de Stirling; números de Fibonacci y números de Catalan; recurrencias; funciones generatrices; y el principio de inclusión-exclusión (PIE). De la teoría de grafos se cubrirán las definiciones básicas de grafos; caminos, caminatas y ciclos; árboles generadores o de expansión; grafos bipartitos; planaridad y el teorema de Kuratowski; grafos Hamiltonianos y Eulerianos.; poliedros; y coloraciones de grafos y el polinomio cromático.

Distribución de las notas

Parciales (60%)

Habrá tres parciales. La fecha de estos se avisará con al menos una semana de anticipación.

Tareas y quizzes (40%)

Habrá tres conjuntos de problemas que se asignarán para cada corte. Trabajar en los problemas de tarea es fundamental para el entendimiento del material presentado en clase. Asegúrese de separar tiempo suficiente de cada semana para pensar y escribir sus soluciones. Se recomienda que le piense e intente cada problema por su propia cuenta antes de buscar ayuda. Se invita a los estudiantes a que discutan el material del curso con sus compañeros, sin embargo cada estudiante debe escribir sus propias soluciones y en sus propias palabras. Pueden haber algunos quizzes que no serán anunciados y también contarán hacia la nota final. La distribución de las tareas según los cortes será de 10% en el primer corte, 10% en el segundo corte, y 20% en el tercer corte.

Sesiones de problemas

Habrá varias sesiones de problemas en clase durante el semestre con el objetivo de reforzar los conceptos aprendidos en cada semana. Durante las sesiones de problemas se invita a los estudiantes a que compartan lo que han aprendido y que aprendan de sus compañeros de clase.

Problemas sugeridos

Habrá también algunos problemas sugeridos adicionales. Estos problemas será asignados en algunas de las clases.

Programa

Este es un programa aproximado del contenido del curso:
FechaTema
Lun 07/26Introducción. ¿Qué es la combinatoria?
Mar 07/27Principios básicos de conteo. Permutaciones y factoriales
Lun 08/02Combinaciones y selecciones
Mar 08/03Combinaciones y selecciones
Lun 08/09Coeficientes binomiales y el triángulo de Pascal
Mar 08/10Selecciones con repeticiones y composiciones
Mar 08/17Un teorema de inversión matricial
Lun 08/23Recurrencias
Mar 08/24Método de la ecuación auxiliar
Lun 08/30Método de la ecuación auxiliar
Mar 08/31Primer Parcial
Lun 09/06Funciones generatrices
Mar 09/07Funciones generatrices
Lun 09/13Desarreglos. Algoritmos de ordenamiento
Mar 09/14Números de Catalan
Lun 09/20Grafos
Mar 09/21Caminos y árboles
Lun 09/27Árboles de expansión
Mar 09/28Árboles de expansión
Lun 10/04Grafos bipartitos. Planaridad
Mar 10/05Poliedros
Lun 10/11Grafos Hamiltonianos
Mar 10/12Segundo Parcial
Lun 10/25Problema del agente viajero
Mar 10/26Grafos Eulerianos
Mar 11/02Particiones
Lun 11/08Particiones
Mar 11/09Coloraciones de grafos y el polinomio cromático
Mar 11/16Principio de Inclusión-Exclusión (PIE)
Mar 11/23Tercer Parcial

Cambios a este programa

Este programa podrá tener algunos cambios durante el semestre. Es responsabilidad del estudiante asistir a clase y visitar frecuentemente la página web del curso para mantenerse actualizado sobre estos cambios.