Matemáticas (plan 1983) 2016-1

Optativas de los Niveles V y VI, Teoría de Gráficas

Este será un curso introductorio —aunque no necesariamente trivial— de teoría de las gráficas, un área de las matemáticas que destaca por ser muy reciente y por estudiar una estructura muy simple. El único prerrequisito es un buen manejo de la inducción matemática.

Temario

El libro de texto será Chromatic Graph Theory de Gary Chartrand y Ping Zhang, el cual pueden consultar aquí, las secciones a las que hace referencia el temario son de este texto También pueden consultar Introduction to Graph Theory de los mismos autores.

1. Introducción §§ 1.1--1.5.
2. Árboles § 2.2.
3. Conexidad §§ 2.1, 2.3--2.4.
4. Apareamientos § 4.1.
5. Recorridos §§ 3.1--3.2.
6. Planaridad § 5.1 y tal vez la § 5.3.
7. Coloraciones § 6.1. La § 6.2 podría ser para exposición.

Tareas

Serán entre cinco y siete tareas que saldrán de los ejercicios correspondientes a las sección del libro del curso.

1. La primer tarea son los problemas impares entre el primero y el vigésimo primero, inclusive, de la lista de ejercicios del capítulo uno del libro y será individual. Se entrega el primero de septiembre.
2. La segunda tarea consiste de los problemas impares entre el vigésimo tercero y el trigésimo séptimo, inclusive, de la lista de ejercicios del capítulo uno del libro y será individual. Se entrega el jueves 10 de septiembre. Para el problema 31, pueden fijar la k y hacer inducción sobre n, preguntándose «¿qué pasa si hay al menos un vértice de grado menor k? ¿y si lo quito?».
3. La tercera tarea consiste en los problemas nones entre el primero y el décimo octavo del capítulo 2. En el ejercicio 13 tienen que escribir las pruebas que les piden. La tarea es individual —ya que tan solo son nueve problemas— y se entregará el miércoles 4 de octubre.
4. La cuarta tarea consiste de los problemas impares entre el décimo octavo y el trigésimo segundo de la lista de ejercicios del capítulo dos del libro y será individual. Se entrega el viernes 23 de octubre.
5. La quinta tarea consiste de los problemas impares del capítulo correspondiente excepto por el noveno. Se entrega el lunes 9 de noviembre.
6. La sexta tarea, que corresponde a apareamientos, se entregará el 19 de noviembre.
7. La séptima y última tarea, que corresponde a coloraciones y planaridad, se entregará el 3 de diciembre.

Evaluación

El piso del promedio de las tareas es el mínimo que pueden obtener como calificación final.