Procurando Árvores Químicas Equi-energéticas

A presente pesquisa tem o objetivo de desenvolver algoritmos e novas idéias que contribuam para a busca por (pares de) grafos com mesma energia, de acordo com algumas definições de energia de grafo. Esta pesquisa restringe-se a uma classe de grafos chamada de Árvores Químicas, definida por ser aqueles que são acíclicos e cujos vértices tem grau no máximo igual a 4. Códigos de alta-performance serão desenvolvidos, conforme este trabalho, que iniciou em Fev 2009, prossegue.

O primeiro programa interativo pode ser encontrado aqui. O correspondente código em C (chamado através de uma interface em PHP) implementa uma chamada a subrotina dspev_ (cálculo de autovalores de matriz simétrica com armazenamento essencial) da biblioteca CLapack.

O segundo programa interativo pode ser encontrado aqui. Esse script implementa um procedimento de busca e classificação em um conjunto de dados que já temos armazenado em um banco de dados MySQL.

Definições de energia sendo usadas:

Dado um grafo $G$, seja $A$ sua matriz de adjacência, seja eig o vetor de autovalores de uma matriz dada, e seja $\vert\cdot\vert _1$ a norma 1 de um vetor (soma dos valores absolutos de suas componentes).

Definimos

$\displaystyle E (G) = \vert \mbox{eig}(A)\vert _1$
a ser chamado simplesmente de energia do grafo $G$.

JBC 19/2/2009,13/5/2010