Teoria Espectral e o Problema de Isomorfismo de Grafos Regulares

Nome: Diego Barcelos Rodrigues
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 29/08/2011
Orientador:

Nomeordem decrescente Papel
Maria Claudia Silva Boeres Co-orientador
Maria Cristina Rangel Orientador

Banca:

Nomeordem decrescente Papel
Arlindo Gomes de Alvarenga Examinador Interno
Maria Claudia Silva Boeres Coorientador
Maria Cristina Rangel Orientador
Nair Maria Maia de Abreu Examinador Externo

Resumo: 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.

Acesso ao documento

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910