Combinatoria y teoría de grafos

Instructor: Rafael S. González D'León
Email: rafael.gonzalezl@usa.edu.co
Homepage: http://dleon.combinatoria.co
Atención a estudiantes: Por cita programada.

Clases

Lunes 4:00-6:00 pm y viernes 6:00-8: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 (30%)

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

Final (30%)

Habrá un exámen final sobre todo el contenido del programa por un valor del 30%.

Tareas y quizzes (40%)

Habrá conjuntos de problemas que se asignarán aproximadamente cada semana y que deberán ser entregados a la semana siguiente. 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 15% en el primer corte, 15% en el segundo corte, y 10% 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 01/22Introducción. ¿Qué es la combinatoria?
Vie 01/26Principios básicos de conteo. Permutaciones y factoriales
Lun 01/29Combinaciones y selecciones
Vie 02/02Combinaciones y selecciones
Lun 02/05Coeficientes binomiales y el triángulo de Pascal
Vie 02/09Selecciones con repeticiones y composiciones
Lun 02/12Selecciones con repeticiones y composiciones
Vie 02/16Un teorema de inversión matricial
Lun 02/19Recurrencias
Vie 02/23Método de la ecuación auxiliar
Lun 02/26Método de la ecuación auxiliar
Vie 03/02Primer Parcial
Lun 03/05Funciones generatrices
Vie 03/09Funciones generatrices
Lun 03/12Desarreglos. Algoritmos de ordenamiento
Vie 03/16Números de Catalan
Vie 03/23Grafos
Lun 04/02Caminos y árboles
Vie 04/06Árboles de expansión
Lun 04/09Árboles de expansión
Vie 04/13Grafos bipartitos. Planaridad
Lun 04/16Poliedros
Vie 04/20Segundo Parcial
Lun 04/23Grafos Hamiltonianos
Vie 04/27Problema del agente viajero
Lun 04/30Grafos Eulerianos
Vie 05/04Particiones
Lun 05/07Particiones
Vie 05/11Coloraciones de grafos y el polinomio cromático
Vie 05/18Principio de Inclusión-Exclusión (PIE)

Política sobre calculadoras

Calculadoras no serán permitidas en quizzes, parciales o exámen final.

Código of conducta

Los estudiantes deben consultar los derechos y debéres del estudiante en el Reglamento estudiantil. Cualquier ofensa a los lineamientos dispuestos por la universidad iniciará los procedimientos disciplinarios establecidos.

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.