Modelo filológico para lenguas romances y germánicas utilizando coloración de gráficas suaves
2015Profesores: Dr. Pedro Lara Velázquez y Dr. Sergio Gerardo de los Cobos Silva
Resumen: El problema de coloración de gráficas suaves busca encontrar una coloración que minimiza la “tensión” en la gráfica, es decir, minimizar la suma de distancias entre vértices con colores idénticos. Este modelo se utiliza en la programación de eventos susceptibles de cambios, asignación estable de frecuencias del espectro electromagnético entre otros. Se ha demostrado que es un problema NP-difícil aunque para instancias pequeñas, máximo de 20 vértices, se utiliza un modelo de programación lineal entera mixto. Para instancias con más de 20 vértices es necesario el uso de técnicas heurísticas que resuelven el problema de forma aproximada. El modelo de este proyecto está basado en el Problema de Coloración de Gráficas Suaves (PCGS) el cual es un caso especial del problema de coloración donde se busca una coloración que minimiza la tensión en la gráfica, es decir, se minimiza la suma total de las tensiones entre los vértices que tienen el mismo color.
Objetivo general
- Crear un modelo filológico para lenguajes romances y germánicos utilizando coloración de gráficas suaves
Objetivos específicos
- Construcción formal del modelo filológico utilizando coloración de gráficas suaves
- Seleccionar la mejor métrica al modelo
- Validar el modelo en un conjunto representativo de lenguas romances
- Validar el modelo en un conjunto representativo de lenguas germánicas
Ultima actualización 13/08/2022 por pcyti