La indecibilidad del clan comportamiento para gráficas finitamente presentadas
14-OAlumno: María del Carmen Cedillo Chagoya
Profesor: Dr. Miguel Ángel Pizaña López
Resumen: Dada una gráfica G, los clanes son las subgráficas completas maximales de G y la gráfica de intersección de éstos es la gráfica de clanes, K(G). Evidentemente el operador de clanes puede ser iterado. Determinar el K-comportamiento de una gráfica G consiste en determinar si G es K-convergente o no. En esta investigación probamos que el K-comportamiento es algorítmicamente irresoluble para el caso de gráficas localmente finitas y finitamente presentadas (pero infinitas).
Objetivo general
- Intentar probar que el problema del clan-comportamiento es irresoluble para gráfi cas infi nitas pero finitamente representadas.
Objetivos específicos
- Intentar mostrar que el operador de clanes es Turing-completo para gráficas infi nitas pero fi nitamente representadas.
- Intentar mostrar que el operador de clanes es Turing-completo para gráfi cas finitas.
- Intentar probar que el problema del clan-comportamiento es irresoluble para gráfi cas fi nitas.
- Desarrollar sotfware para la experimentación con problemas de teoría de gráfi cas.
- Principalmente se desarrollará la parte de visualización del software llamado Yags (Yet Another Graphs System).
- Desarrollo de un manual técnico para Yags.
- Experimentación en Yags con algoritmos genéticos.
- Experimentar en Yags diversos problemas en teoría de clanes y en teoría de gráfi cas.
Ultima actualización 25/07/2022 por pcyti