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:
Nome |
Papel |
|---|---|
| MARIA CLAUDIA SILVA BOERES | Co-orientador |
Banca:
| Nome |
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.
