Made available in DSpace on 2016-12-23T14:33:46Z (GMT). No. of bitstreams: 1
Dissertacao de Diego Barcelos Rodrigues.pdf: 434389 bytes, checksum: 1deed45ceca5ef4fe6169aeed7e5e4d5 (MD5)
Previous issue date: 2011-08-29 / Spectral 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 / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace2.ufes.br:10/6411 |
| Date | 29 August 2011 |
| Creators | Rodrigues, Diego Barcelos |
| Contributors | Rangel, Maria Cristina, Alvarenga, Arlindo Gomes de, Abreu, Nair Maria Maia de, Boeres, Maria Claudia Silva |
| Publisher | Universidade Federal do Espírito Santo, Programa de Pós-Graduação em Informática, UFES, BR, Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | text |
| Source | reponame:Repositório Institucional da UFES, instname:Universidade Federal do Espírito Santo, instacron:UFES |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0026 seconds