Use este identificador para citar ou linkar para este item: http://bdex.eb.mil.br/jspui/handle/123456789/9130
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorJustel, Claudia Marcela-
dc.contributor.authorSilva, Anderson Chaves da-
dc.date.accessioned2021-05-20T13:45:48Z-
dc.date.available2021-05-20T13:45:48Z-
dc.date.issued2018-
dc.identifier.urihttp://bdex.eb.mil.br/jspui/handle/123456789/9130-
dc.descriptionDissertação (Mestrado em Engenharia da computação)pt_BR
dc.description.abstractA teoria espectral de grafos busca identificar características dos grafos a partir da observação dos espectros de diferentes matrizes associadas aos mesmos. Um importante problema nesta área é conhecido como o Problema do Aumento Máximo da Conectividade Algébrica. O mesmo consiste em, dado um grafo maximizar o valor do parâmetro denominado conectividade algébrica através da adição do menor número de arestas possível. Uma vez que este problema é NP-Completo, existem na literatura algoritmos visando obter soluções aproximadas. Neste trabalho apresentamos os resultados de experimentos comparativos entre dois destes algoritmos: a heurística de perturbação, HP, e a heurística de excentricidade, HE. Apresentamos também resultados teóricos, os quais descrevem casos em que a inserção de arestas não aumenta a conectividade algébrica. Efetuamos os experimentos em duas classes de árvores: árvores double broom - em particular, uma subfamília das mesmas, as árvores broom - e uma subfamília da classe das árvores starlike. Para realizar os experimentos desenvolvemos um sistema na linguagem Python que permite efetuar comparações entre os resultados das heurísticas. Para as árvores double broom, os resultados obtidos nos experimentos com a HE, considerando até 2 arestas a serem inseridas, revelaram em todos os casos avaliados um aumento da conectividade algébrica maior ou igual aos da HP. Para as árvores broom, o aumento obtido pela HE considerando 1 aresta a ser inserida foi sempre maior que o resultado obtido pela HP. Ao serem inseridas 2 arestas, a HE é proporcionou um aumento maior em quase todos os experimentos realizados para as árvores broom. A partir dos experimentos realizados, foi possível identificar algumas arestas as quais, quando inseridas não proporcionavam aumento da conectividade algébrica.pt_BR
dc.language.isopt_BRpt_BR
dc.subjectConectividade algébricapt_BR
dc.subjectGrafospt_BR
dc.titleProblema do aumento da conectividade algébrica em classes particulares de grafospt_BR
dc.typeDissertaçãopt_BR
dc.rights.licenseEste exemplar é de propriedade do Instituto Militar de Engenharia, que poderá incluí-lo em base de dados, armazenar em computador, micro filmar ou adotar qualquer forma de arquivamento. É permitida a menção, reprodução parcial ou integral e a transmissão entre bibliotecas deste trabalho, sem modificação de seu texto, em qualquer meio que esteja ou venha a ser fixado, para pesquisa acadêmica, comentários e citações, desde que sem finalidade comercial e que seja feita a referência bibliográfica completa. Os conceitos expressos neste trabalho são de responsabilidade do autor e dos orientadores.pt_BR
Aparece nas coleções:DCT: IME: PUBLICAÇÕES ACADÊMICAS

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Dissertação - Anderson Chaves da Silva.pdf1,25 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.