Matemáticas (plan 1983) 2015-2

Grupo 4799 56 alumnos.

 

Ilán A. Goldfeder (ilan (at) ciencias.unam.mx)

Jana Dosal (loiretalejandria (at) ciencias.unam.mx)

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.

1. Introducción a gráficas (6 semanas)

1.0 Introducción.

1.1 Noción de gráfica (gráfica, vértice, aristas, relación de adyacencia, vecindades, grados, etc).

* Clases de digráficas.

1.2 Subgráficas (subgrafica, s. inducida y s. generadora).

1.3 Isomorfismo de gráficas.

1.4 Caminos y conexidad.

1.5 Algunos resultados sobre conexidad, caminos, ciclos y hojas.

Tareas:

(0) Tarea de inducción. Se entrega el jueves 12 de febrero.

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

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

• Ejercicios: 27-33, 36, 38-49. Se aplican los mismos criterios que en la tarea 1, sobre los puntajes para la calificación de esta tarea, tanto en modo individual como en pareja.

2. Árboles (2 semanas)

2.1 Caracterización de los árboles.

2.2 Árboles generadores.

(3) Tercera tarea. Se entrega el jueves 26 de marzo.

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) Cuarta tarea. Se entrega el jueves 16 de abril.

4. Recorridos (dos 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).

(5) Quinta tarea. Se entrega el jueves 30 de abril.

5. Apareamientos (2 semanas)

5.1 Apareamientos en gráficas.

5.2 Lema de Berge.

5.3 Teorema de Hall.

(6) Sexta tarea. Se entrega el jueves 14 de mayo.

6. Coloración y planaridad (2 semanas)

6.1 Coloraciones en gráficas.

6.2 Gráficas planas.

(7) Séptima tarea. Se entrega el jueves 21 de mayo.

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.

É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.