Use of Automorphisms in Conauto-2.0

Núñez Chiroque, Luis Felipe (2011). Use of Automorphisms in Conauto-2.0. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.U.I.T. Telecomunicación (UPM) [antigua denominación].

Descripción

Título: Use of Automorphisms in Conauto-2.0
Autor/es:
  • Núñez Chiroque, Luis Felipe
Director/es:
  • López Presa, José Luis
Tipo de Documento: Proyecto Fin de Carrera/Grado
Fecha: 28 Octubre 2011
Materias:
Escuela: E.U.I.T. Telecomunicación (UPM) [antigua denominación]
Departamento: Ingeniería y Arquitecturas Telemáticas [hasta 2014]
Licencias Creative Commons: Reconocimiento

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa

Resumen

Se ha realizado un estudio de los fundamentos matemáticos de la teoría de grafos, la cual tiene varios problemas abiertos. Uno de estos problemas es el del isomorfismo de un subgrafo, del cual podemos sacar un caso particular de él, que es el problema del isomorfismo de grafos. El problema del isomorfismo de grafos tiene interés, tanto desde el punto de vista teórico, como práctico. Desde el punto de vista teórico es interesante porque existen variedad de problemas que son reducibles al del isomorfismo de grafos. Por lo tanto, encontrar un algoritmo que resuelva este problema en tiempo polinómico, resolvería indirectamente estos otro problemas también en tiempo polinómico. Desde el punto de vista práctico, resulta útil en muchos campos, desde el reconocimiento de formas a la química matemática, donde es imprescindible para catalogar adecuadamente los compuestos químicos. Partiendo del algoritmo conauto-1.02, se han añadido nuevas funcionalidad, conservando el enfoque original, para mejorar su rendimiento. Los más actuales y rápidos algoritmos para resolver el problema del isomorfismo de grafos están basados en etiquetado canónico. Sin embargo, normalmente es mucho más difícil encontrar un etiquetado canónico para un grafo, que calcular su grupo de automorfismo. Por lo tanto, un algoritmo que calcule el grupo de automorfismo de los grafos a comprobar dicho isomorfismo, e intente casarlos usando esta información, podría dar lugar a un algoritmo que sea más rápido que aquellos basados en etiquetado canónico. Con todo esto, hemos desarrollado un algoritmo, conauto-2.0, que usa este enfoque alternativo. Una característica en común de todos estos algoritmo (incluido conauto) es que están basados en la técnica de individualización-refinamiento. Los puntos clave en la individualización son los criterios para seleccionar la celda de la cual se individualizará un vértice. En conauto-2.0 la selección de la celda para individualizar es parcialmente dinámica, e intenta reducir el número de puntos de 'backtrack' tanto como le sea posible. Esto es una contribución parcial de este trabajo, pero que ayuda a mejorar el rendimiento. Las más importantes contribuciones de este trabajo son los teoeremas basados en el concepto de sub-partición. El primer teorema permite la detección prematura de automorfismos sin la necesidad de generar la correspondiente secuencia de particiones completa, lo cual acelera el algoritmo en muchos casos. El segundo teorema ayuda a podar secciones completas del árbol de búsqueda para los casos de búsqueda de automorfismos y la búsqueda de secuencia de particiones compatibles, usando 'backjumping'. Estas características de conauto-2.0 lo hacen superar al resto de algoritmos con las familias de grafos basados en componentes, y además su campo de aplicación no está solamente limitado a estas familias de grafos. Se realizaron pruebas de isomorfismo de grafos y de cálculo de grupo de automorfismo para nuestro algoritmo, contra algunos de los actuales y más conocidos algoritmos de resolución de dichos problemas. Los resultados mostraron que conauto-2.0 tiene el comportamiento más regular, además de ser el algoritmo más rápido para varias familias de grafos.

Más información

ID de Registro: 10045
Identificador DC: http://oa.upm.es/10045/
Identificador OAI: oai:oa.upm.es:10045
Depositado por: Sr. Luis Felipe Núñez Chiroque
Depositado el: 15 Ene 2012 16:21
Ultima Modificación: 20 Abr 2016 18:19
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM