Tesis profesional presentada por

Juan Ricardo Rugerio Bretón [juan.rugeriobn@udlap.mx] Marco Antonio Sánchez Ortega

Miembro del programa de honores. Licenciatura en Actuaría. Departamento de Actuaría, Física y Matemáticas. Escuela de Ciencias, Universidad de las Américas Puebla.

Jurado Calificador

Presidente: Dra. Dolores Edwiges Luna Reyes
Vocal y Director: Dr. Juan Antonio Díaz García
Secretario: Dra. Luz María García Ávila

Cholula, Puebla, México a 7 de diciembre de 2018.

Resumen

El Problema de Coloreado de Grafos es un problema de optimización combinatoria ampliamente estudiado en la literatura, ya que muchos problemas de aplicación práctica se pueden formular como problemas de Coloreado de Grafos. Ejemplos de estos son la programación de tareas, la asignación de frecuencias en redes o la asignación de registros de memoria de una computadora. Dado que el problema pertenece a la clase de problemas NP-duro, se justifica el uso de métodos heurísticos para obtener soluciones factibles del...

Palabras clave: Optimización Heurísticas Coloreado de Grafos Número cromático.

Resumen.

Índice de contenido

Portada

Índices

Capítulo 1. Introducción

Capítulo 2. Justificación

Capítulo 3. Objetivos

Capítulo 4. Marco Teórico

  • 4.1 Historia
  • 4.2 Trabajos destacados
  • 4.3 Algoritmos voraces
  • 4.4 Algoritmos basados en el mejoramiento de una solución inicial
  • 4.5 Métodos exactos
  • 4.6 Métodos Híbridos
  • 4.7 Aplicaciones

Capítulo 5. Metodología

  • 5.1 Descripción del problema
  • 5.2 Modelo matemático
  • 5.3 k-Coloreado
  • 5.4 Algoritmos voraces
  • 5.5 Búsqueda Local
  • 5.6 Temple Simulado

Capítulo 6. Implementaciones

  • 6.1 Algoritmo Secuencial: SEQ
  • 6.2 Algoritmo Recursivo RLF
  • 6.3 Algoritmo basado en la metodología de temple simulado
  • 6.4 Instancias

Capítulo 7. Resultados y Discusión

  • 7.1 Estadístico para la comparación de métodos
  • 7.2 Análisis e interpretación

Capítulo 8. Conclusiones y Recomendaciones

Referencias

Documento completo (archivo pdf, 257 kb)

Rugerio Bretón, J. R., Sánchez Ortega, M. A. 2018. Comparación de métodos heurísticos para el problema de Coloreado de Grafos. Tesis Licenciatura. Actuaría. Departamento de Actuaría, Física y Matemáticas, Escuela de Ciencias, Universidad de las Américas Puebla. Diciembre. Derechos Reservados © 2018.