Gráficas y juegos

El presente curso de «Gráficas y juegos» tiene dos objetivos; el primero es dar una introducción a la Teoría de las Gráficas, a sus objetos de estudio y a resultados importantes sobre ellos y el segundo es servir de ejercicio al razonamiento matemático. En el curso se le da particular énfasis al desarrollo formal de la teoría así como al uso de la inducción matemática como método de prueba.

Temario

(1) Primera tarea. Se entrega el jueves 26 de febrero.

Ejercicios: 1-11, 13, 18-26. Lee, piensa y responde con cuidado. No olvides argumentar bien tus respuestas y recordar las definiciones (a veces son lo más importante). No se copien, pues ejercicios isomorfos se cancelan (no es difícil percatarse de cuando dos ejercicios son isomorfos, sobre todo cuando copian los mismos errores).
- Tarea individual. El número de puntos que reúnan será la calificación de su tarea, con un máximo de 12.
- Tarea en pareja. Se aplicará un factor de 2/3 (es decir, necesitan 15 puntos para obtener diez y 18 puntos para obtener 12).

(2) Segunda tarea. Se entrega el viernes 20 de marzo.

Ejercicios: 27-33, 36, 38-49. Lee, piensa y responde con cuidado. No olvides argumentar bien tus respuestas y recordar las definiciones (a veces son lo más importante). No se copien, pues ejercicios isomorfos se cancelan (no es difícil percatarse de cuando dos ejercicios son isomorfos, sobre todo cuando copian los mismos errores).
- Tarea individual. El número de puntos que reúnan será la calificación de su tarea, con un máximo de 12.
- Tarea en pareja. Se aplicará un factor de 2/3 (es decir, necesitan 15 puntos para obtener diez y 18 puntos para obtener 12).

I. Primer examen, martes 24 de febrero.

2. Árboles (2 semanas)

2.1 Caracterización de los árboles.

2.2 Árboles generadores.

(3) Tercera tarea, hay una pequeña modificación. Se entrega el miércoles 15 de abril.

3. Conexidad en gráficas (2 semanas)

3.1 Vértices y aristas de corte.

3.2 Bloques.

3.3 Conexidad puntual y lineal.

4. Recorridos (2 semanas)

4.1 Recorridos eulerianos (caracterización de las gráficas que poseen un paseo euleriano cerrado y abierto).

4.2 Recorridos hamiltonianos (condiciones suficientes para la existencia de ciclos hamiltonianos).

(4) Cuarta tarea. Se entrega el lunes 18 de mayo.

5. Apareamientos (2 semanas)

5.1 Apareamientos en gráficas.

5.2 Lema de Berge.

5.3 Teorema de Hall.

6. Coloración y planaridad (2 semanas)

6.1 Coloraciones en gráficas.

6.2 Gráficas planas.

(*) Última tarea. Se entrega el primer día de junio.

Evaluación

Evaluaremos por medio de ocho tareas-examen, cuyas fechas de entrega ya están fijadas. Quienes tengan un promedio mínimo de ocho quedarán exentos del examen final y ésa será su calificación final del curso. Para quienes presenten el examen final, la calificación final será el promedio del promedio de las tareas y el examen final.

Calificaciones.

Consideraciones finales

Ésta es la lista de ejercicios de donde saldrán, eventualmente, la mayoría de las tareas. Nos encontramos a su disposición para cualquier duda que tengan.

Libros disponibles en la red

Graph Theory with Applications de Bondy

Graph Theory de Diestel

Gráficas y juegos

Primeros conceptos

Introducción

Temario

Evaluación

Consideraciones finales

Libros disponibles en la red