Please use this identifier to cite or link to this item: http://repositorio.ufes.br/handle/10/4240
Title: Teoria Espectral e o Problema de Isomorfismo de Grafos Regulares
metadata.dc.creator: RODRIGUES, D. B.
Keywords: Problema de Isomorfismo de grafos;Teoria Espectral de Grafo
Issue Date: 29-Aug-2011
Publisher: Universidade Federal do Espírito Santo
Citation: RODRIGUES, D. B., Teoria Espectral e o Problema de Isomorfismo de Grafos Regulares
Abstract: 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.
URI: http://repositorio.ufes.br/handle/10/4240
Appears in Collections:PPGI - Dissertações de mestrado

Files in This Item:
File Description SizeFormat 
tese_4174_.pdf422.41 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.