Problema do aumento da conectividade algébrica em classes particulares de grafos

Abstract

A 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.