Energia do grafo

Os primeiros estudos sobre a energia de grafos se deram no inicio dos anos 30, tendo origem em pesquisas sobre química quântica . Nestes trabalhos, grafos foram utilizados para representar moléculas de hidrocarbonetos, com o propósito de determinar os níveis energéticos de alguns elétrons. Estas informações eram obtidas através da soma dos módulos dos autovalores do grafo associado a molécula em questão. Contudo, a energia de um grafo foi definida pela primeira vez apenas em 1978 por Ivan Gutman.

Definição

Em teoria espectral de grafos, a energia de um grafo é um parâmetro definido como a soma dos valores absolutos dos autovalores da sua matriz de adjacência. Mais precisamente, sejam ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_n$ todos os autovalores da matriz de adjacência do grafo $G$. Assim, sua energia é definida como:

$E(G)=\sum _{i=1}^n|{\lambda }_i|,$

Energia de uma matriz

Nikiforov estendeu o conceito de energia de um grafo para matrizes reais. Considere $M$a matriz real (não necessariamente quadrada), sua energia é definida como a soma dos seus valores singulares. Vamos recordar que um valor singular da matriz $M$, é a raiz quadrada de um dos autovalores da matriz $M{M}^T$. Mais precisamente, sejam ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_n$ todos os valores de singulares de $M$, assim a sua energia é definida por:

$E(M)=\sum _{i=1}^n{\sigma }_i$

Nestas condições, vale destacar que a energia de um grafo $G$, é igual a energia da sua matriz de adjacência.

Outras energias

Além da energia usual de um grafo $G$, atualmente pesquisadores tem estudado energias associadas a outras matrizes relacionadas com um grafo. Seja $G$ um grafo com $n$ vértices e $m$ arestas e $I$ é a matriz identidade . Assim definimos:

A energia Laplaciana, definida como $LE(G)=E(L(G)-\frac{2m}{n}I)$, onde $L(G)$ é matriz Laplaciana do grafo $G$.

A energia Laplaciana sem sinal, definida como $QE(G)=E(Q(G)-\frac{2m}{n}I)$, onde $Q(G)$ é matriz Laplaciana sem sinal do grafo $G$.

A energia de incidência, definida como $BE(G)=E(B(G))$, onde $B(G)$ é matriz de incidência do grafo $G$.