Matemáticas (plan 1983) 2022-2

Optativas de los Niveles VII y VIII, Seminario Matemáticas Aplicadas I

CURSO AVANZADO DE TEORÍA DE GRÁFICAS: TEORÍA CROMÁTICA Y MODELACIÓN

Para obtener acceso al calssroom del grupo envía un correo a loiretalejandria@ciencias.unam.mx

Objetivos del curso:

Que el alumno conozca y aprenda diversos tipos de coloración en gráficas, explore y profundice en la teoría cromática y aplique estos conocimientos en la modelación de problemas concretos, comprendiendo así, la importancia y necesidad de los diferentes tipos defunciones de coloración.

Prerrequisitos:

El alumno debe de haber cursado previamente el primer curso de Teoría de Gráficas o en su defecto Gráficas y Juegos, y sería deseable aunque no indispensable haber cursado Teoría de las Gráficas II.

Metodología:

Trabajaremos mediante exposiciones colaborativas, en donde los estudiantes eligirán un tema de su interés a desarrollar, tanto en el aspecto teórico como en el trabajo de modelación; cada uno de los temas que revisemos durante el semestre se abordará con énfasis en algún problema de aplicación.

Contenido:

• Nociones clásicas de coloración:

  1. Número cromático de una gráfica

  2. Teorema de Brooks

  3. Teorema de Vizing

  4. Gráficas perfectas

  5. Gráficas - perfectas

2. Coloraciones Ramsey:

   1. Números de Ramsey (repaso con aplicaciones)

   2. Números de Ramsey Arcoiris

3. Coloración fraccional:

   1. Gráficas - multi coloreables

   2. Número cromático fraccional

   3. Homomorfismos y gráficas de Knesser

4. Coloraciones totales:

   1. Gráficas k-coloreables totalmente

   2. Número cromático total

5. Coloraciones completas:

   1. El número acromático de una gráfica

   2. H-coloraciones y H-caminos

   3. El número de Grundy de una gráfica

6. Coloraciones y algoritmos:

   1. Polinomio cromático

   2. Coloraciones glotonas

   3. El algoritmo glotón

REFERENCIAS:

• Bundy, J. A. & Murty, U. S. R. Graph Theory. Springer (2008).

• Chartrand, G.; Lesniak, L.& Zhang, P. Graphs & Digraphs. USA: CRC Press. (2015).

• Chartrand, G. & Zhang, P. Chromatic Graph Theory. USA: CRC Press. (2008).

• Gross, J. L. & Yellen, J. Graph Theory and its Applications. Chapman & Hall/CRC(2006).

• Hell, P. & Nesetril, J. Graphs and homomorphisms. Oxford (2004).

• Matula, D. W.; Marble, G. Isaacson, J. D. Graph Coloring Algorithms. Graph Theory and Computing, 109–122 (1972).

• Roberts, F. S. Graph Theory and its Applications to Problems of Society. SIAM (1978).

• Scheinerman, E. R. & Ullman, D. H. Fractional Graph Theory: A rational approach to the Theory of Graphs. Dover. (2008).

Forma de evaluación:

• Exposición - Planteamiento y modelación de problema de aplicación: 80%

• Participación en las sesiones 20% (La asistencia no es obligatoria; en el sentido de que no se contabilizan las asistencias, pero dada la dinámica del curso, es deseable constancia y presencia durante el semestre).