Mostrar código-fonte de Teoria espectral de grafos

[[Image:Complete-edge-coloring.svg|thumb|350px|O [[grafo completo]] com 8 vértices possui espectro {7,-1,-1,-1,-1,-1,-1,-1} .]]

Em matemática, a '''teoria espectral de grafos''' estuda propriedades de um [[grafos|grafo]] por meio de suas representações matriciais e de seus respectivos [[Espectro_(matemática)|espectros]]. Em geral, a Teoria Algébrica dos Grafos estuda propriedades algébricas de funções de representação e operações em grafos, conceitos e propriedades algébricas delas decorrentes. Além disso, em Teoria Espectral de Grafos, estudam-se as propriedades estruturais decorrentes das matrizes que representam grafos. Estas últimas levam às propriedades espectrais das matrizes de representação, que é o elemento central da teoria espectral de grafos.

==Breve Histórico==
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.<ref name="cvet2">''Eigenspaces of Graphs'', by [[Dragoš Cvetković]], Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1</ref> A monografia  ''Spectra of graphs'' de 1980,<ref>Dragoš M. Cvetković, Michael Doob, [[Horst Sachs]], ''Spectra of Graphs'' (1980)</ref> 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''.<ref>{{citar livro|primeiro1 =Dragoš M.|último1 =Cvetković |primeiro2 =Michael |último2 =Doob |primeiro3 =Horst |último3 =Sachs |primeiro4 =A. |último4 =Torgasev |título=Recent Results in the Theory of Graph Spectra |series=Annals of Discrete mathematics |número=36 |ano=1988 |isbn=0-444-70361-6 |url=http://www.sciencedirect.com/science/bookseries/01675060/36}}</ref> A 3 ª edição do  ''Spectra of graphs'' (1995) contém um resumo das contribuições mais recentes para o assunto.<ref name= cvet2/>

==Matriz de Adjacência==
O estudo da Teoria Espectral dos Grafos basicamente relaciona propriedades algébricas do espectro de certas matrizes associadas
a 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  <math>A(G)=[a_{ij}]</math>,  onde  <math>a_{ij}=1</math> se <math>v_iv_j \in E</math> e <math>a_{ij}=0</math> nas entradas restantes. Quando conveniente, utilizaremos apenas A para denotar a matriz de adjacência.
Eis um exemplo:
{|class="wikitable"
!Grafo rotulado
!Matriz de Adjacência
|-
|[[Ficheiro:6n-graph2.svg|200px|right]]
|<math>\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}</math>
|}
O espectro de G
é o conjunto dos autovalores, geralmente apresentados em ordem decrescente, não
necessariamente no sentido estrito, associados às suas respectivas multiplicidades
algébricas.

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

Grafos isospectrais não precisam ser [[Isomorfismo_de_grafos|isomorfos]], mas os grafos isomorfos são isoespectrais. O menor par de grafos não isomorfos  e cospectrais não dirigidos são {''K''<sub>1,4</sub>, ''C''<sub>4</sub> U ''K''<sub>1</sub>}, como relatado por Collatz e Sinogowitz<ref>Collatz, L. and Sinogowitz, U. "Spektren endlicher Grafen." Abh. Math. Sem. Univ. Hamburg 21, 63&ndash;77, 1957.</ref><ref>{{mathworld|CospectralGraphs|Cospectral Graphs}}</ref> em 1957.

Quase todas as [[árvore (teoria dos grafos)|árvores]] são coespectrais, ou seja, a proporção de árvores cospectrais em '''n''' vértices tende a 1 quando '''n''' cresce.<ref>[[A. J. Schwenk|Schwenk, A. J.]] "Almost All Trees are Cospectral"  In:
''New Directions in the Theory of Graphs'' (F. Harary, Ed.), Academic Press, New York, 1973, pp. 275&#x2013;307.</ref>

===Energia do Grafo===
Se ''A'' é a  [[matriz de adjacência]] do grafo ''G'', a [[energia do grafo]] é definida como:

:<math>E(G) = \sum_{i=1}^n|\lambda_i|</math>

onde <math>\lambda_i</math>, <math> i = 1, 2, \ldots , n </math>  são os autovalores de ''A''. A energia de um grafo foi definida pela primeira vez por [[Ivan Gutman]] em 1978.<ref>[[Richard A. Brualdi]], [http://www.public.iastate.edu/~lhogben/energyB.pdf Energy of a Graph] {{Wayback|url=http://www.public.iastate.edu/~lhogben/energyB.pdf|date=20111203142344}}, AIM Workshop, 2006.</ref>

==Matriz Laplaciana==
Dado um grafo G=(V,E) com '''n''' vértices, a [[matriz Laplaciana]] de G é a matriz de ordem '''n''' dada por  <math>L(G)=[l_{ij}]</math>,  onde  <math>l_{ij}=-1</math> se <math>v_iv_j \in E</math>, <math>l_{ii}=d(v_i)</math> e <math>l_{ij}=0</math> 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
:<math>L=D-A </math>
onde <math>D</math> é a [[matriz diagonal]] com o grau dos vértices.

Eis um exemplo:

{|class="wikitable"
!Grafo rotulado
!Matriz laplaciana
|-
|[[Imagem:6n-graf.svg|175px]]
|<math>\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}</math>
|}

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,<ref>''Laplacian Matrices of Graphs: A Survey'', by [[R. Merris]], Linear Algebra and its Applications, Vol. 197 (1994), 198:143-176.</ref> alguns dos muitos resultados
conhecidos 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 <math>{l_1}\le{l_2}\le{...}\le{l_n}</math> os autovalores de L. Então:

(i) <math>{l_1} = 0</math> e o vetor com todas entradas iguais a 1 é autovetor associado

(ii) G é conexo se, e somente se, <math>{l_2} > 0</math>.''

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.

===Teorema da Matriz-Árvore===
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.''

===Conectividade algébrica===
[[Image:Truncatedicosahedron.gif|thumb|O [[icosaedro truncado]], visto como um grafo, possui conectividade de vértices 3, porém conectividade algébrica de 0,243.]]

Fiedler mostrou<ref>''Algebraic connectivity of graphs'', by [[Miroslav Fiedler]], Czechoslo-
vak Mathematical Journal, Vol. 23 (1973), 298-305.</ref> 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), &kappa;(G) e &lambda;(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) ≤ &kappa;(G) ≤ &lambda;(G).''

Para o grafo completo <math>{K_n}</math>, Fiedler demonstrou que <math>a({K_n})= n</math>.


===Energia Laplaciana do Grafo===
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.<ref>[[Ivan Gutman]], [http://www.aimath.org/WWN/matrixspectrum/gutman2006.pdf Laplacian Energy of a Graph], Linear Algebra and its Applications, 414, (2006), 29–37.</ref>
Considerando ''L'' a  [[matriz Laplaciana]] do grafo ''G'' com ''n'' vértices e ''m'' arestas, a [[energia Laplaciana do grafo]] é definida como:

:<math>E(G) = \sum_{i=1}^n\left|\lambda_i-\frac{2m}{n}\right|</math>

onde <math>\lambda_i</math>, <math> i = 1, 2, \ldots , n </math>  são os autovalores de ''L''.

==Matriz Laplaciana normalizada==

A matriz Laplaciana normalizada pode ser definida por <ref name="mathworld">{{MathWorld |urlname=LaplacianMatrix |title=Laplacian Matrix}}</ref>

:<math>\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}
</math>

A matriz Laplaciana normalizada <math>\ell</math> e a matriz Laplaciana <math>L</math> se relacionam da seguinte forma
:<math>
\ell = D^{1/2}LD^{1/2}
</math>
onde <math>D</math> diagonal com o grau dos vértices.

{{referências}}

==Ver também==
*[[Matriz de adjacência]]
*[[Conectividade algébrica]]
*[[Energia do grafo]]

{{Portal3|Matemática}}

[[Categoria:Álgebra linear]]
[[Categoria:Combinatória]]
[[Categoria:Teoria dos grafos]]


{{esboço-matemática}}