Teoria Espectral de Grafos Aplicada ao Problema de Isomorfismo de Grafos

Nome: Philippe Leal Freire dos Santos
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 23/08/2010
Orientador:

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

Banca:

Nomeordem decrescente Papel
Lucia Catabriga Examinador Interno
Maria Claudia Silva Boeres Coorientador
Maria Cristina Rangel Orientador
Nair Maria Maia de Abreu Examinador Externo

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

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