Teoria espectral de grafos

Teoria Espectral de Grafos surgiu nos anos 1950 e 1960. Além das pesquisas em Teoria dos Grafos sobre a relação entre as propriedades estruturais e espectrais de grafos, outra fonte importante foi a pesquisa em química quântica, mas as conexões entre essas duas linhas de trabalho foram descobertos muito mais tarde.^[1] A monografia Spectra of graphs de 1980,^[2] por Cvetkovic, Doob, e Sachs resumiu quase todas as pesquisas até o momento na área. Em 1988, ela foi atualizada pelo survey em Teoria Espectral de Grafos Recent Results in the Theory of Graph Spectra.^[3] A 3 ª edição do Spectra of graphs (1995) contém um resumo das contribuições mais recentes para o assunto.^[1]

O estudo da Teoria Espectral dos Grafos basicamente relaciona propriedades algébricas do espectro de certas matrizes associadasa um grafo e as propriedades estruturais desse grafo. A associação mais comum éfeita pela matriz de adjacência e o espectro dessa matriz é o espectro do grafo.Dado um grafo G=(V,E) com n vértices, a matriz de adjacência de G é a matriz de ordem n dada por ${\displaystyle A(G)=[a_{ij}]}$ , onde ${\displaystyle a_{ij}=1}$ se ${\displaystyle v_{i}v_{j}\in E}$ e ${\displaystyle a_{ij}=0}$ nas entradas restantes. Quando conveniente, utilizaremos apenas A para denotar a matriz de adjacência.Eis um exemplo:

Grafo rotulado	Matriz de Adjacência
	${\displaystyle {\begin{bmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{bmatrix}}}$

O espectro de Gé o conjunto dos autovalores, geralmente apresentados em ordem decrescente, nãonecessariamente no sentido estrito, associados às suas respectivas multiplicidadesalgébricas.

Uma das questões em aberto da Teoria de Grafos se refere à caracterização deuma lista completa de parâmetros capaz de decidir se dois grafos são isomorfos.Tais parâmetros são conhecidos como invariantes do grafo.Dois grafos são chamados de isoespectrais ou cospectrais se a matriz de adjacência de cada grafo tem os mesmos autovalores.

Grafos isospectrais não precisam ser isomorfos, mas os grafos isomorfos são isoespectrais. O menor par de grafos não isomorfos e cospectrais não dirigidos são {K_1,4, C₄ U K₁}, como relatado por Collatz e Sinogowitz^[4][5] em 1957.

Quase todas as árvores são coespectrais, ou seja, a proporção de árvores cospectrais em n vértices tende a 1 quando n cresce.^[6]

Se A é a matriz de adjacência do grafo G, a energia do grafo é definida como:

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

onde ${\displaystyle \lambda _{i}}$ , ${\displaystyle i=1,2,\ldots ,n}$ são os autovalores de A. A energia de um grafo foi definida pela primeira vez por Ivan Gutman em 1978.^[7]

Dado um grafo G=(V,E) com n vértices, a matriz Laplaciana de G é a matriz de ordem n dada por ${\displaystyle L(G)=[l_{ij}]}$ , onde ${\displaystyle l_{ij}=-1}$ se ${\displaystyle v_{i}v_{j}\in E}$ , ${\displaystyle l_{ii}=d(v_{i})}$ e ${\displaystyle l_{ij}=0}$ nas entradas restantes. Quando conveniente, utilizaremos apenas L para denotar a matriz laplaciana.

A matriz Laplaciana e a matriz de adjacência se relacionam da forma

${\displaystyle L=D-A}$

onde ${\displaystyle D}$ é a matriz diagonal com o grau dos vértices.

Eis um exemplo:

Grafo rotulado	Matriz laplaciana
	${\displaystyle {\begin{bmatrix}2&-1&0&0&-1&0\\-1&3&-1&0&-1&0\\0&-1&2&-1&0&0\\0&0&-1&3&-1&-1\\-1&-1&0&-1&3&0\\0&0&0&-1&0&1\\\end{bmatrix}}}$

Uma representação de um grafo frequente em teoria espectral de grafos é dada pela sua matriz Laplaciana. Essa matriz e, em especial, o seu segundo menor autovalor, chamado de conectividade algébrica, desempenham um papel relevante em diversas aplicações. Em,^[8] alguns dos muitos resultadosconhecidos sobre essa matriz são exibidos.

A seguir, enunciamos um resultado bem conhecido sobre o primeiro e o segundo menor autovalor laplaciano de um grafo G.

Teorema

Seja G um grafo com n vértices, e L sua matriz laplaciana. Sejam ${\displaystyle {l_{1}}\leq {l_{2}}\leq {...}\leq {l_{n}}}$ os autovalores de L. Então:

(i) ${\displaystyle {l_{1}}=0}$ e o vetor com todas entradas iguais a 1 é autovetor associado

(ii) G é conexo se, e somente se, ${\displaystyle {l_{2}}>0}$ .

Portanto todos os autovalores de L são maiores ou iguais a zero. Para um grafo desconexo, o número de autovalores iguais a zero é precisamente o número de componentes conexas do grafo. Assim, a multiplicidade do autovalor zero é o número de componentes conexas de G.

Outro resultado importante envolvendo a matriz Laplaciana é o teorema da matriz-árvore. Uma árvore geradora de um grafo G é um subgrafo que tem os mesmos vértices de G e é uma árvore. A determinação do número de árvores geradoras de um grafo é um dos problemas mais antigos e famosos da teoria de grafos.

Em 1847, Kirchhoff estudando circuitos elétricos, provou o resultado que ficou conhecido como teorema da matriz-árvore, enunciado a seguir.

Claramente, grafos desconexos não possuem árvores geradoras. Por outro lado, todo grafo conexo tem pelo menos uma árvore geradora (se o grafo não é uma árvore, podemos remover uma aresta de cada ciclo, sucessivamente, até não haver mais ciclos. O subgrafo obtido será uma árvore geradora do grafo inicial). O teorema da matriz-árvore, na sua versão original, afirma que o número de árvores geradoras de um grafo é dado por qualquer cofator de sua matriz laplaciana. Mais precisamente:

Teorema

adj(L) = t(G) · J, onde t(G) é o número de árvores geradoras de G, e J é a matriz com todas entradas iguais a 1.

Fiedler mostrou^[9] que um grafo é conexo se, e somente se, o seu segundo menor autovalor Laplaciano é positivo. Esse autovalor é denominado conectividade algébrica e desempenha um papel fundamental em teoria espectral de grafos. Denotamos a conectividade algébrica por a(G).

As conectividades algébrica, de vértices e de arestas, respectivamente a(G), κ(G) e λ(G), estão relacionadas de acordo com o resultado abaixo, provado por Fiedler.

Teorema

Se G não é um grafo completo então a(G) ≤ κ(G) ≤ λ(G).

Para o grafo completo ${\displaystyle {K_{n}}}$ , Fiedler demonstrou que ${\displaystyle a({K_{n}})=n}$ .

Da mesma maneira que para a matriz de adjacência, a energia pode ser definida utilizando os autovalores da matriz Laplaciana. Esse conceito também foi definido por Ivan Gutman em 2006 no artigo.^[10]Considerando L a matriz Laplaciana do grafo G com n vértices e m arestas, a energia Laplaciana do grafo é definida como:

${\displaystyle E(G)=\sum _{i=1}^{n}\left|\lambda _{i}-{\frac {2m}{n}}\right|}$

onde ${\displaystyle \lambda _{i}}$ , ${\displaystyle i=1,2,\ldots ,n}$ são os autovalores de L.

A matriz Laplaciana normalizada pode ser definida por ^[11]

${\displaystyle \ell _{i,j}:={\begin{cases}1&{\mbox{if}}\ i=j\ {\mbox{and}}\ \deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}}$

A matriz Laplaciana normalizada ${\displaystyle \ell }$ e a matriz Laplaciana ${\displaystyle L}$ se relacionam da seguinte forma

${\displaystyle \ell =D^{1/2}LD^{1/2}}$

onde ${\displaystyle D}$ diagonal com o grau dos vértices.

• Matriz de adjacência
• Conectividade algébrica
• Energia do grafo

• Portal da matemática

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e