Matemáticas (plan 1983) 2024-2

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

¡Te damos la bienvenida al Seminario de Matemáticas Aplicadas I 2024-2 de Teoría Algorítmica de las Gráficas!

Título: TEORÍA ALGORÍTMICA DE LAS GRÁFICAS

Profra. Loiret Dosal

Aviso: la primera clase será el miércoles. No habrá clase el lunes ni el martes.

Código de classroom:iqiglnp

Motivación: La Teoría de Gráficas es una rama de la matemática discreta que estudia las estructuras que forman un conjunto de objetos y sus relaciones entre ellos, debido a su naturaleza son extremadamente útiles para modelar problemas del mundo real, tales como la planificación eficiente de rutas de transporte, el análisis de situaciones estratégicas empresariales, la distribución eficiente de recursos, la gestión de una cadena de suministros, el análisis de incompatibilidad de horarios, el análisis de redes de flujo vehicular para minimizar la congestión vial, el diseño eficiente de redes de comunicación, el análisis y prevención de las vulnerabilidades en una red informática, entre muchos otros. La Teoría Algorítmica de las Gráficas se centra en analizar la eficiencia y complejidad de los algoritmos aplicados en diversos problemas que pueden ser modelados mediante conceptos de la Teoría de Gráficas, con el objetivo de comprender la naturaleza y el rendimiento de dichos algoritmos, y así facilitar la resolución de esta clase de problemas.

Objetivos generales del curso: El propósito principal de este curso es que las y los estudiantes adquieran habilidades en la resolución de problemas complejos a través de la implementación de técnicas algorítmicas especializadas en el contexto de la Teoría de Gráficas, desarrollando una comprensión profunda de los conceptos fundamentales de la Teoría Algorítmica de las Gráficas, para ser aplicados en el abordaje de desafíos en diversas disciplinas.

Objetivos específicos del curso:

Se desea que las y los estudiantes:

• Apliquen los conceptos de la Teoría de Gráficas en la modelación de problemas del mundo real.

• Aprendan a evaluar la complejidad de los algoritmos y comprendan la teoría de la NP-completitud.

• Sean capaces de implementar, analizar y diseñar algoritmos eficientes para la resolución de problemas específicos, que puedan ser modelados mediante la estructura de una gráfica.

Prerrequisitos: Las y los estudiantes deben 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 de trabajo: Las y los estudiantes realizarán las siguientes actividades de aprendizaje durante el semestre:

• Exposición

• Tareas-Examen

• Proyecto colaborativo

La exposición a realizar puede ser individual o en parejas a elegir entre los temas que se proponen en el Temario y que se enlistan más adelante. Las tareas - examen se refieren a pequeñas listas cortas de ejercicios de los temas expuestos, y el objetivo del proyecto colaborativo es implementar los conocimientos adquiridos en la resolución de algún problema concreto de la vida real, mediante el trabajo y la discusión colaborativa.

Evaluación del curso: Las actividades antes mencionadas se ponderarán de la siguiente manera:

• Exposición 50%

• Tareas - Examen 30%

• Proyecto colaborativo 20%

Temario (horas aproximadas):

1. Introducción a la Teoría Algorítmica de Gráficas (10 horas)

1.1. Tipos de gráficas: dirigidas, no dirigidas, ponderadas, etc.

1.2. Modelación de problemas con Teoría de Gráficas

1.3 Complejidad algorítmica y problemas NP-completos

1.4 Algoritmos de búsqueda y ordenamiento

1.5 Algoritmos glotones

2. Árboles (10 horas)

2.1. Algoritmos de búsqueda de profundidad (DFS)

2.2. Algoritmos de búsqueda de anchura (BFS)

2.3. Árboles generadores de peso mínimo: algoritmos de Prim y Kruskal

3. Distancia en Gráficas (10 horas)

3.1. Algoritmos de búsqueda de trayectorias mínimas

3.2. Algoritmo de Dijkstra para gráficas pesadas

3.3. Algoritmo de trayectorias críticas en digráficas

4. Flujos en redes, digráficas y conexidad (14 horas)

4.1. Teorema de flujo máximo - corte mínimo

4.2. Algoritmo de Ford-Fulkerson

4.3. Algoritmo de trayectorias críticas en digráficas

4.4 Algoritmo de análisis de conexidad

4.5 Algoritmo de búsqueda de componentes fuertes en digráficas

5. Apareamientos (12 horas)

5.1. Teorema de König

5.2. Algoritmo de apareamiento máximo en gráficas bipartitas

5.3. Algoritmo de Kuhn-Munkers para gráficas bipartitas completas pesadas

6. Recorridos en gráficas (12 horas)

6.1. Algoritmo de circuitos eulerianos

6.2. Problema del cartero chino

6.3. Modelación de problemas con digráficas eulerianas

6.4 El problema del hombre viajero

6.5 Algoritmo para determinar ciclos hamiltonianos de peso mínimo en gráficas completas pesadas

7. Coloración y planaridad (12 horas)

7.1. Teorema de Kuratowski

7.2 Algoritmos de test de planaridad en bloques

7.3 Teorema de Brooks

7.4 Algoritmo glotón para colorear vértices de una gráfica

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. & Oellermann, O. R. Applied and Algorithmic Graph Theory. McGraw-Hill (1993).

● Bang-Jensen, J. & Gutin, G. Digraphs: Theory, Algorithms and Applications. Springer-Verlag (2007).

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

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

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