La indecibilidad del clan comportamiento para gráficas finitamente presentadas

Alumno: 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 graáficas infi nitas pero fi nitamente representadas.
  • Intentar mostrar que el operador de clanes es Turing-completo para graáficas 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.
    • Experimentacion en Yags con algoritmos genéticos.
  • Experimentar en Yags diversos problemas en teoría de clanes y en teoría de gráfi cas.

Última actualización: May 29, 2016 at 19:32 pm

Síntesis de voz basada en Modelos Ocultos de Markov y algoritmos de aprendizaje profundo

Regresar a Proyectos de investigación para alumnos de Doctorado

P C y T I