Teoria espectral e o problema de isomorfismo de grafos regulares

Página do item simplificado
dc.contributor.advisor-co1Boeres, Maria Claudia Silva
dc.contributor.advisor1Rangel, Maria Cristina
dc.contributor.authorRodrigues, Diego Barcelos
dc.contributor.referee1Alvarenga, Arlindo Gomes de
dc.contributor.referee2Abreu, Nair Maria Maia de
dc.date.accessioned2016-12-23T14:33:46Z
dc.date.available2012-01-20
dc.date.available2016-12-23T14:33:46Z
dc.date.issued2011-08-29
dc.description.abstractSpectral Graph Theory (SGT) studies graph properties by graph representation matrix and its spectrum. A property from SGT, the eigencentrality, provides an important invariant to Graph Isomorphism Problem: if two graphs are isomorphic, they have proportional eigencentralities. However, this property can not be directly used for solving the Regular Graph Isomorphism Problem (RGIP), as every regular graph has the same eigencentralities. This work presents a strategy for solving the RGIP through the use of eigencentralities to prune the search tree and restricting the possibilities for mapping.eng
dc.description.resumoA 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,
dc.formatText
dc.identifier.citationRODRIGUES, Diego Barcelos. Teoria espectral e o problema de isomorfismo de grafos regulares. 2011. 84 f. Dissertação (Mestrado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico, Vitória, 2011.
dc.identifier.urihttp://repositorio.ufes.br/handle/10/6411
dc.languagepor
dc.publisherUniversidade Federal do Espírito Santo
dc.publisher.countryBR
dc.publisher.courseMestrado em Informática
dc.publisher.departmentCentro Tecnológico
dc.publisher.initialsUFES
dc.publisher.programPrograma de Pós-Graduação em Informática
dc.rightsopen access
dc.subjectIsomorphismeng
dc.subjectSpectroeng
dc.subjectEigencentralityeng
dc.subjectEspectropor
dc.subjectAutocentralidadepor
dc.subject.br-rjbnIsomorfismos (Matemática)
dc.subject.br-rjbnAnálise espectral
dc.subject.cnpqCiência da Computação
dc.subject.udc004
dc.titleTeoria espectral e o problema de isomorfismo de grafos regulares
dc.typemasterThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertacao de Diego Barcelos Rodrigues.pdf
Tamanho:
424.21 KB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Coleções
Mestrado em Informática