Made available in DSpace on 2016-08-29T15:33:12Z (GMT). No. of bitstreams: 1 tese_3542_.pdf: 1219514 bytes, checksum: 46e780a84760376a53aff9fb5e279285 (MD5) Previous issue date: 2010-08-23 / Neste trabalho investigamos a utilização de conceitos da Teoria Espectral de Grafos (TEG) a fim de auxiliar a construção de algoritmos que solucionem o Problema de Isomorfismo de Grafos (PIG). Três resultados teóricos que consideram informações do espectro e das centralidades de autovetor dos vértices dos grafos foram presentados. Além disso, foi proposto um algoritmo para detecção de isomorfismo de grafos baseado em dois destes resultados. Por fim, apresentamos os resultados computacionais da comparação deste algoritmo com outros da literatura.

Made available in DSpace on 2016-08-29T15:33:15Z (GMT). No. of bitstreams: 1 tese_4174_.pdf: 432544 bytes, checksum: 56e998c1c8c4b2e3ad13cf3720cfbe5f (MD5) Previous issue date: 2011-08-29 / A Teoria Espectral de Grafos (TEG) busca analisar propriedades dos grafos através de matrizes representativas de grafos e seus espectros. De uma propriedade proveniente da TEG, a autocentralidade, surge um importante invariante para o Problema de Isomorfismo de Grafos: se dois grafos são isomorfos então eles possuem autocentralidades proporcionais. Porém, esta propriedade não pode ser usada diretamente para resolução do Problema de Isomorfismo de Grafos Regulares (PIGR), pois todo grafo regular possui autocentralidades iguais. Este trabalho apresenta uma estratégia para resolver o PIGR através do uso das autocentralidades para podar a árvore de busca e restringir as possibilidades de mapeamento.