Teoria Espectral de Grafos - Uma Introdução III … · Figura 2 – Um grafo 4-regular. •grafo completo: É o grafo no qual quaisquer dois vértices distintos são adjacentes

N. Abreu, R. Del-Vecchio, V. Trevisan, C. Vinagre

Teoria Espectral de Grafos - Uma

Introdução

IIIo Colóquio de Matemática da Região

Sul

Florianópolis, SC

2014

N. Abreu, R. Del-Vecchio, V. Trevisan, C. Vinagre

Teoria Espectral de Grafos - Uma IntroduçãoIIIo Colóquio de Matemática da Região Sul

Minicurso apresentado no IIIoColóquio de Matemática daRegião Sul, realizado na Univer-sidade Federal de Santa Cata-rina, em maio de 2014.

Florianópolis, SC

2014

Resumo

A Teoria Espectral de Grafos busca analisar propriedades estru-turais de grafos através de matrizes e seus espectros, ou seja,dos autovalores das matrizes associadas a eles. O marco ini-cial desta teoria é o trabalho de Hückel em química quântica,de 1931, mas foi a partir da tese de doutorado de Cvetković,em 1971, que a teoria teve um grande desenvolvimento. Nesteminicurso, investigaremos algumas matrizes associadas a grafose mostraremos sua utilização na modelagem de problemas emdiversas áreas do conhecimento. Particularmente estudaremos amatriz de adjacência, a matriz de incidência, a matriz Laplacianae a matriz Laplaciana sem sinal. Além disso, apresentaremos al-goritmos para a localização de autovalores para algumas classesde grafos.

Este texto é uma versão revista e bastante ampliada das No-tas de Matemática Aplicada 27, “Introdução à Teoria Espectralde Grafos com Aplicações”, publicada pela SBMAC (SociedadeBrasileira de Matemática Aplicada e Computacional) em 2007(1a edição) e 2012 (2a edição, formato de e-book), ver [2].

Palavras-chaves: Espectro de grafo, polinômio característico,matriz Laplaciana, matriz de adjacência, matriz Laplaciana semsinal.

Lista de ilustrações

Figura 1 – Grafo do Exemplo 1.1 . . . . . . . . . . . . . 14Figura 2 – Um grafo 4-regular. . . . . . . . . . . . . . . . 15Figura 3 – K4. . . . . . . . . . . . . . . . . . . . . . . . . 15Figura 4 – C3 e P5. . . . . . . . . . . . . . . . . . . . . . 16Figura 5 – G1 é um grafo conexo e G2 é desconexo. . . . . 16Figura 6 – Uma floresta com 3 árvores. . . . . . . . . . . . 17Figura 7 – K3,4. . . . . . . . . . . . . . . . . . . . . . . . 17Figura 8 – K4 e seu grafo-linha ℓ(K4). . . . . . . . . . . . 18Figura 9 – Um grafo e seu complementar. . . . . . . . . . . 18Figura 10 – 3K4. . . . . . . . . . . . . . . . . . . . . . . . 19Figura 11 – G1 ×G2. . . . . . . . . . . . . . . . . . . . . . 20Figura 12 – Grafo do Exemplo 1.2 . . . . . . . . . . . . . . 21Figura 13 – Grafo de Petersen. . . . . . . . . . . . . . . . . 22Figura 14 – Grafo para o Exercício 5. . . . . . . . . . . . . 23Figura 15 – Grafo do Exemplo 2.1. . . . . . . . . . . . . . . 29Figura 16 – Grafos com mesmo p(λ) e ciclos diferentes. . . . 32Figura 17 – O hiperoctaedro H5. . . . . . . . . . . . . . . . 45Figura 18 – Ci(6, 2), Ci(6, 1, 3), Ci(6, 1, 2) e Ci(6, 2, 3). . . . 47Figura 19 – M5 (Möbius Ladder com 10 vértices) . . . . . . 51Figura 20 – G1 e G2 são grafos isomorfos. . . . . . . . . . . 53Figura 21 – G1 e G2 são grafos não isomorfos e coespectrais. 53Figura 22 – Hidrocarboneto e grafo que o representa. . . . . 56Figura 23 – Grafos cúbicos de ordem 10 . . . . . . . . . . . 66Figura 24 – Um grafo pipa. . . . . . . . . . . . . . . . . . . 67Figura 25 – Cubo . . . . . . . . . . . . . . . . . . . . . . . 68Figura 26 – Grafo do Exemplo 3.1. . . . . . . . . . . . . . . 72

Figura 27 – Grafo do Exemplo 3.2 . . . . . . . . . . . . . . 75Figura 28 – Grafo do Exemplo 4.1 . . . . . . . . . . . . . . 82Figura 29 – Grafos G1 e G2. . . . . . . . . . . . . . . . . . 83Figura 30 – K4 e suas 16 árvores geradoras. . . . . . . . . . 87Figura 31 – A estrela K1,6 tem µ1 = 7. . . . . . . . . . . . 102Figura 32 – Grafos Laplacianos-coespectrais não isomorfos. . 103Figura 33 – Grafo do Exemplo 4.10 . . . . . . . . . . . . . 104Figura 34 – Contraexemplo de Grone e Merris . . . . . . . . 105Figura 35 – Grafos do Exemplo 4.11. . . . . . . . . . . . . 106Figura 36 – Grafo do Exemplo 4.12 . . . . . . . . . . . . . 107Figura 37 – Grafo do Exemplo 4.14 . . . . . . . . . . . . . 113Figura 38 – Isômeros do octano: m1 é o índice do Laplaciano. 115Figura 39 – Estrutura secundária do RNA . . . . . . . . . . 116Figura 40 – Grafo da estrutura secundária do RNA. . . . . . 117Figura 41 – Árvores de ordem 8 e conec. alg. crescentes. . . . 117Figura 42 – Grafo do Exercício 1. . . . . . . . . . . . . . . 119Figura 43 – Grafo do Exercício 2. . . . . . . . . . . . . . . 119Figura 44 – K5 ∨K9 é um grafo Q-integral . . . . . . . . 134Figura 45 – G é Q-integral mas G não é. . . . . . . . . . 135Figura 46 – Índice de incerteza: G coespectrais até 11 vértices. 137Figura 47 – Índice de incerteza de A(G), G até 21 vértices. . 138Figura 48 – Índice de incerteza de L(G) com G até 21 vértices. 139Figura 49 – Número de autovalores em (α, β]. . . . . . . . 147Figura 50 – Localizando o maior autovalor. . . . . . . . . 148Figura 51 – Vértice vk com filho vj e pai vl . . . . . . . . 148Figura 52 – Diagonalizando A+ αI. . . . . . . . . . . . . 153Figura 53 – Dois autovalores positivos. . . . . . . . . . . . 154Figura 54 – Todos os autovalores menores que 2. . . . . . 154Figura 55 – Um autovalor maior que 1. . . . . . . . . . . 155Figura 56 – Dois autovalores maiores que 1

2 . . . . . . . . 155

Figura 57 – Centopeia diagonalizada com α = 0 . . . . . 156Figura 58 – Construção de um grafo threshold . . . . . . 159Figura 59 – Diagonalizing A(G) + xI. . . . . . . . . . . . 167

Lista de tabelas

Tabela 1 – Alguns grafos para os quais a(G) é conhecido. . 101Tabela 2 – a(G′), para G′ um grafo obtido de G. . . . . . . 101Tabela 3 – Incertezas coespectrais de A e Q, G até 11 vértices.137Tabela 4 – Índices coespectrais para A(T ), L(T ) e A(T )&L(T ).140

Sumário

1 Preliminares sobre grafos . . . . . . . . . . . 131.1 Conceitos básicos . . . . . . . . . . . . . . . . 131.2 Relações entre alguns parâmetros de grafos . . 201.3 Exercícios . . . . . . . . . . . . . . . . . . . . 231.4 Notas bibliográficas . . . . . . . . . . . . . . . 24

2 Matriz de adjacência . . . . . . . . . . . . . 272.1 Introdução . . . . . . . . . . . . . . . . . . . . 272.2 Polinômio característico e espectro de um grafo 282.3 Alguns resultados e aplicações . . . . . . . . . 332.4 O espectro de certos tipos de grafos . . . . . . 412.4.1 Grafos circulantes e seus espectros . . . . . . . 472.5 Isomorfismo de Grafos . . . . . . . . . . . . . 522.6 Energia de grafos . . . . . . . . . . . . . . . . 562.6.1 Limites para a energia de um grafo . . . . . . 582.7 Exercícios . . . . . . . . . . . . . . . . . . . . 652.8 Notas bibliográficas . . . . . . . . . . . . . . . 69

3 Matriz de incidência . . . . . . . . . . . . . . 713.1 Introdução . . . . . . . . . . . . . . . . . . . . 713.2 Matriz de incidência e grafo-linha de um grafo 713.3 Exercícios . . . . . . . . . . . . . . . . . . . . 773.4 Notas bibliográficas . . . . . . . . . . . . . . . 79

4 Matriz Laplaciana . . . . . . . . . . . . . . . 814.1 Conceitos e resultados preliminares . . . . . . 814.2 O Teorema da Matriz-árvore . . . . . . . . . . 864.3 Conectividade algébrica . . . . . . . . . . . . . 100

4.4 Autovalores e o problema do corte maximal . 1054.4.1 Corte maximal e autovalores em certos grafos 1084.5 Aplicações . . . . . . . . . . . . . . . . . . . . 1144.5.1 Carbonos quaternários e grau máximo . . . . 1144.5.2 RNA e conectividade algébrica . . . . . . . . . 1154.5.3 Potencial de ionização . . . . . . . . . . . . . 1184.6 Exercícios . . . . . . . . . . . . . . . . . . . . 1184.7 Notas bibliográficas . . . . . . . . . . . . . . . 121

5 Matriz Laplaciana sem sinal . . . . . . . . . 1235.1 Matriz Laplaciana sem sinal . . . . . . . . . . 1235.2 Q-espectro da união, produto cartesiano e “join” 1295.3 Grafos Q-integrais . . . . . . . . . . . . . . . . 1325.4 Coespectralidade e aplicações . . . . . . . . . 1355.5 Exercícios . . . . . . . . . . . . . . . . . . . . 1415.6 Notas bibliográficas . . . . . . . . . . . . . . . 142

6 Algoritmos de Localização de Autovalores . 1456.1 Motivação . . . . . . . . . . . . . . . . . . . . 1456.2 Adjacência de árvores . . . . . . . . . . . . . . 1486.3 Aplicações para árvores . . . . . . . . . . . . . 1536.3.1 Exemplo . . . . . . . . . . . . . . . . . . . . . 1536.3.2 Centopeias . . . . . . . . . . . . . . . . . . . . 1556.4 Adjacências de grafos threshold . . . . . . . . 1576.4.1 Diagonalizando A+ xI . . . . . . . . . . . . . 1596.4.2 Exemplos . . . . . . . . . . . . . . . . . . . . . 1666.4.3 Simplicidade dos autovalores . . . . . . . . . . 1706.5 Exercícios . . . . . . . . . . . . . . . . . . . . 1716.5.1 Notas Bibliográficas . . . . . . . . . . . . . . . 172

Referências . . . . . . . . . . . . . . . . . . . 173

7 Apêndice . . . . . . . . . . . . . . . . . . . . 183

7.1 Um resultado de Teoria de Matrizes . . . . . . 1837.2 Resultados sobre matrizes simétricas . . . . . 1867.2.1 Princípio de Rayleigh . . . . . . . . . . . . . . 1867.2.2 Teorema de Entrelaçamento . . . . . . . . . . 1887.2.3 Partições equilibradas . . . . . . . . . . . . . . 1907.2.4 Teorema de Sylvester para a inércia . . . . . . 1917.2.5 Teorema de Perron-Frobenius . . . . . . . . . 194

Índice . . . . . . . . . . . . . . . . . . . . . . 199

1 Preliminares sobre grafos

Neste capítulo apresentamos as noções básicas e a ter-minologia própria da Teoria de Grafos estritamente necessáriasà compreensão do restante do trabalho. Apresentamos tambémalguns parâmetros de grafos e certas relações entre eles.

1.1 Conceitos básicos

Definição 1.1. Um grafo é uma estrutura G = G(V,E), cons-tituída por um conjunto finito e não vazio V cujos elementos sãodenominados vértices, e um conjunto E de subconjuntos a doiselementos de V denominados arestas. Indicamos por |V | e |E|,respectivamente, o número de vértices e o número de arestas deG . Se u, v ∈ V e e = {u, v} ∈ E , dizemos que a aresta e

incide em u e v. O grau de um vértice v, denotado pord(v), é o número de arestas que incidem em v. Vértices liga-dos por arestas são ditos vértices adjacentes. Quando V é umconjunto unitário e E = ∅ dizemos que G é o grafo trivial.

No que se segue, consideramos apenas grafos sem arestasligando um vértice a ele mesmo (laços), sem arestas múltiplas(mais de uma aresta incidindo no mesmo par de vértices) e semorientação. Estes grafos são chamados grafos simples, mas nosreferiremos a eles como grafos.


Exemplo 1.1. No grafo da Figura1 1 , V = {v1, v2, v3, v4, v5}e E = {e1, e2, e3, e4, e5, e6}, e portanto |V | = 5 e |E| = 6. Asarestas são e1 = {v1, v2}, e2 = {v2, v3}, e3 = {v4, v5}, e4 =

{v1, v4}, e5 = {v1, v5} e e6 = {v2, v5}. Os vértices v1 e v2 sãoadjacentes mas v1 e v3 são não adjacentes. Os graus dos vérticessão: d(v1) = d(v2) = d(v5) = 3, d(v3) = 1 e d(v4) = 2.

Figura 1 – Grafo do Exemplo 1.1

Definição 1.2. Seja G = G(V,E) um grafo. Quando G′ =

G′(V ′, E′) é um grafo satisfazendo V ′ ⊂ V e E′ ⊂ E escrevemosG′ ⊂ G e dizemos que G′ é um subgrafo de G. Quando G′ ⊂ G

é tal que dois vértices são adjacentes em G′ se e somente se elessão adjacentes em G, dizemos que G′ é um subgrafo induzidode G.

Apresentamos a seguir alguns tipos especiais de grafosque aparecerão ao longo deste trabalho.

1 Os grafos deste trabalho foram, em sua maioria, desenhados com o soft-ware yEd Graph Editor [82].

1.1 Conceitos básicos 15

• grafo regular de grau k ou k-regular : É um grafoem que todos os vértices têm o mesmo grau k. A Figura 2mostra um grafo 4-regular.

Figura 2 – Um grafo 4-regular.

• grafo completo: É o grafo no qual quaisquer dois vérticesdistintos são adjacentes. Para cada n ≥ 1, o grafo completocom n vértices é (n − 1)-regular e denotado por Kn. NaFigura 3, vemos o grafo K4.

Figura 3 – K4.

• cadeias, caminhos e ciclos: Uma sequência finita v1, v2,

v3 . . . , vk de vértices de um grafo G(V,E) é dita umacadeia (walk) de v1 a vk quando {vi, vi+1} ∈ E para1 ≤ i ≤ k − 1 . Dizemos que v1, v2, . . . , vk é uma cadeia


fechada (respectivamente, cadeia aberta) quando v1 =

vk (respectivamente, v1 ̸= vk). Um caminho (path) é umacadeia em que todos os vértices são distintos. Um caminhofechado é denominado ciclo. O comprimento de umcaminho ou de um ciclo é o número de arestas queocorrem em cada um. O caminho e o ciclo com n vérticessão denotados, respectivamente, por Pn e Cn. Em partic-ular, o ciclo C3 é chamado triângulo, ver Figura 4 .

Figura 4 – C3 e P5.

Figura 5 – G1 é um grafo conexo e G2 é desconexo.

• grafo conexo: É um grafo no qual existe um caminholigando cada par de vértices. Em caso contrário, o grafoé denominado desconexo. Se G é um grafo desconexo,dizemos que G′ ⊂ G é uma componente conexa de G

quando G′ é um grafo conexo e não existe um grafo conexoH ⊂ G tal que G′ ⊂ H e G′ ̸= H . Na Figura 5, o grafo G1


é conexo e G2 é um grafo desconexo com três componentesconexas.

• árvore: É um grafo conexo e sem ciclos. Um grafo desco-nexo e sem ciclos é chamado uma floresta (ver Figura 6).

Figura 6 – Uma floresta com 3 árvores.

• grafo k-partido: É um grafo G = G(V,E) no qual existeuma partição do conjunto de vértices V em k subconjuntosnão vazios e disjuntos dois a dois (isto é, V = Y1 ∪ . . . ∪Yk, com Yi ∩ Yj = ∅, para todo i ̸= j), de modo que asarestas de G sejam da forma {p, q} com p em Yi e q emYj . Portanto, não há vértices adjacentes em um mesmosubconjunto da partição. Quando k = 2, temos um grafobipartido e quando k = 3, temos um grafo tripartido.Em particular, árvores são grafos bipartidos.

Figura 7 – K3,4.


• grafo bipartido completo: É um grafo G = G(V1∪V2, E)

bipartido em que cada vértice de V1 é adjacente a todovértice de V2. Se |V1| = r e |V2| = s, escrevemos G = Kr,s.O grafo do tipo K1,n é chamado estrela. O grafo K3,4

pode ser visto na Figura 7.

Figura 8 – K4 e seu grafo-linha ℓ(K4).

• grafo-linha: É o grafo ℓ(G) obtido do grafo G tomandoas arestas de G como vértices de ℓ(G) e ligando dois vér-tices em ℓ(G) quando as arestas correspondentes em G

possuírem um vértice comum. É fácil ver que se G é umgrafo regular de grau k então ℓ(G) é um grafo regular degrau 2k−2. Na Figura 8, notar que K4 é 3-regular e ℓ(K4)

é 4-regular.

Figura 9 – Um grafo e seu complementar.


• grafo complementar : É o grafo G = G(V ,E) obtido deG = G(V,E) de tal forma que V = V e {vi, vj} ∈ E se esomente se {vi, vj} /∈ E (ver Figura 9).

Operações entre grafos permitem obter grafos a partirde grafos dados. Dentre as várias existentes, neste texto trabal-haremos com a união de grafos, o produto cartesiano e o joinde grafos (estas duas últimas somente no Capítulo 5). No quese segue, G1 = G1(V1, E1) e G2 = G2(V2, E2) são dois grafosdados:

• união de G1 e G2: Quando V1 ∩ V2 = ∅, o grafo uniãoG1 ∪ G2 é aquele cujo conjunto de vértices é V1 ∪ V2 eo conjunto de arestas é E1 ∪ E2. Este grafo é tambémchamado soma de G1 e G2 e neste caso, denotado G1+G2.

Para qualquer grafo conexo G, escrevemos kG para indicaro grafo que é a união de k cópias de G. A Figura 10 mostraa união de 3 cópias de K4, ou seja, 3K4.

Figura 10 – 3K4.

• produto completo ou junção (“join“) de G1 e G2: Éo grafo G1 ∨G2 obtido de G1 ∪G2 unindo-se cada vérticede G1 a todos os vértices de G2. Portanto, o seu conjunto

de vértices é dado pela união de V1 e V2. Observemos queG1 ∨G2 = G1 ∪G2.

• produto cartesiano de G1 e G2: É o grafo G1 × G2,cujo conjunto de vértices é V = V1 × V2 e no qual doisvértices (u1, u2) ∈ V e (v1, v2) ∈ V são adjacentes se, esomente se, u1 é adjacente a v1 em G1 e u2 = v2 em G2

ou u1 = v1 em G1 e u2 é adjacente a v2 em G2.

Figura 11 – G1 ×G2.

1.2 Relações entre alguns parâmetros de grafos

Definição 1.3. Seja G = G(V,E) um grafo. O grau mínimode G é o número δ = min{d(v) : v ∈ V }. O número △ =

max{d(v) : v ∈ V } é chamado grau máximo de G e

d =1

|V |∑v∈V

d(v)

é chamado grau médio de G.

1.2 Relações entre alguns parâmetros de grafos 21


Exemplo 1.2. O grafo da Figura 12 possui δ = 1, △ = 3 ed = 2, 4.

As seguintes relações são imediatas a partir das definições:

δ ≤ d ≤ △ e d =2|E||V |

.

Definição 1.4. Seja G um grafo conexo. Se x e y são vérticesde G, chamamos distância de x a y e denotamos por d(x, y),ao mínimo dos comprimentos dos caminhos que ligam x a y.O máximo das distâncias entre dois vértices quaisquer de G échamado diâmetro de G e denotado por diam(G). Quando G éum grafo desconexo escrevemos diam(G) =∞ .

Proposição 1.1. O número de vértices de um grafo G comdiâmetro D é no máximo igual a 1 +△+△(△− 1) +△(△−1)2 + . . .+△(△− 1)D−1 .

Demonstração: Tomemos um vértice v1 do grafo G. Este vérticeestá ligado no máximo a △ outros vértices. Cada um destesvértices pode estar ligado, no máximo, a △ − 1 vértices (poiseles estão ligados a v1), acrescentando então no máximo, △(△−1) vértices. Podemos prosseguir sucessivamente deste modo por

D − 1 vezes, chegando assim ao resultado desejado, qual seja,

|V | ≤ 1 +△+△(△− 1) +△(△− 1)2 + . . .+△(△− 1)D−1 .

Definição 1.5. Quando G = G(V,E) tem diâmetro D e satisfaz

|V | = 1 +△+△(△− 1) +△(△− 1)2 + . . .+△(△− 1)D−1,

dizemos que G é um grafo de Moore.

Exemplo 1.3. O grafo da Figura 13 pode ser descrito comoℓ(K5) e tem |V | = 10, △ = 3 e diâmetro D = 2. É um exemplode grafo de Moore conhecido como grafo de Petersen.

Figura 13 – Grafo de Petersen.

Existem poucos grafos de Moore. Um problema impor-tante de grafos, conhecido como problema do grau-diâmetro, é ode encontrar o grafo com grau máximo △, diâmetro D e o maiornúmero de vértices possível. J-C Bermond, C. Delorme e J. J.Quisquater apresentam em [7] uma tabela com △ variando de3 a 16, e D variando de 2 a 10, onde, em cada caso, exibem osgrafos com o maior número de vértices.

1.3 Exercícios 23

1.3 Exercícios

1. Prove que a soma dos graus dos vértices de um grafo éduas vezes o número de suas arestas.

2. Mostre que em todo grafo o número de vértices de grauímpar é sempre par.

3. Prove que o complementar de um grafo desconexo é conexo.

4. Para cada i, 1 ≤ i ≤ n, seja di ∈ N. Prove que d1 ≥ d2

≥ · · · ≥ dn é a sequência de graus de uma árvore se esomente se dn > 0 e

∑ni=1 di = 2(n− 1).

5. Prove que todo grafo conexo tem diâmetro finito e deter-mine o diâmetro do grafo da Figura 14.

Figura 14 – Grafo para o Exercício 5.

6. Construa o grafo-linha do grafo dado na Figura 14.

7. Mostre que se ℓ(G) é o grafo-linha de um grafo G entãoℓ(G) não pode ter K1,3 como subgrafo induzido.

8. Mostre que o grafo completo de ordem 5 sem uma aresta,K5 − {e}, não é grafo-linha de nenhum grafo.

9. Construa todas as árvores com 8 vértices cujo diâmetro é4.

10. Mostre que um grafo é bipartido se e somente se todo cicloinduzido tem comprimento par.

11. Seja G um grafo e G−{v} o grafo obtido de G pela retiradade um de seus vértices. Se G− {v} = K1,3, determine G.

12. Qual é o número máximo de arestas de um grafo simplese conexo? Determine o(s) grafo(s) que atende(m) a estapropriedade. Responda às mesmas questões para o númeromínimo de arestas.

13. Desenhe uma representação para cada grafo com 4 vér-tices. Verifique quantas delas representam grafos conexos.Quantas representam grafos sem ciclos como seus subgrafosinduzidos? Dentre estas, quantas árvores há?

14. Prove que se um grafo com m arestas e n vértices temm > n2

4 arestas então ele não é bipartido.

15. Os grafos 3-regulares são conhecidos como grafos cúbi-cos. Para n ≥ 3, construa um grafo cúbico sem triângulose com 2n vértices.

1.4 Notas bibliográficas

Os primeiros livros em Teoria dos Grafos surgiram aofinal dos anos 60 e início dos anos 70. Hoje a literatura é vasta erica, com uma série de bons títulos, o que torna mais fácil a tarefade uma boa indicação, mas quase impossível a tarefa de apresen-tar a melhor lista de referências aos leitores mais interessados.Recomendamos, então, os livros de Bollobás [12], Diestel [34]

1.4 Notas bibliográficas 25

e Harary [50], não somente por serem de autores consagrados,mas principalmente porque, através deles, estudantes de gradu-ação, com alguma base em Matemática, podem se iniciar nestalúdica e fértil área de pesquisa. Dentre uma série de livros e títu-los em grafos que abordam estrutura de dados computacionaise descrevem algoritmos e suas complexidades, recomendamos osbons textos em português de Markenzon & Szwarcfiter [80] eMarkenzon & Vernet [66], para o primeiro caso, e o de Szwar-cfiter [79], mais específico para algoritmos computacionais. Há,também, uma tão vasta bibliografia voltada para aplicações emodelos em grafos que ficaria difícil uma indicação. No entanto,gostaríamos de citar o livro de Boaventura Netto [11], cuja uti-lização se tornou tradicional nos cursos das escolas brasileiras deEngenharia de Produção e afins.

27

2 Matriz de adjacência

Neste capítulo apresentaremos algumas das técnicas uti-lizadas para deduzir propriedades estruturais de grafos a partirdos coeficientes do seu polinômio característico e do seu espectro,isto é, dos autovalores da matriz de adjacência.

2.1 Introdução

A matriz de adjacência é a matriz de zeros e uns que seconstrói naturalmente a partir das relações de adjacência entreos vértices do grafo. Na primeira seção deste capítulo, apresenta-mos os conceitos preliminares associados a esta matriz e algumasdas técnicas utilizadas para deduzir propriedades estruturais degrafos a partir dos coeficientes do seu polinômio característicoe do seu espectro. Ainda nesta seção apresentamos algumas re-lações entre os autovalores da matriz de adjacência e os parâmet-ros de grafos introduzidos no Capítulo 1 e fazemos uma breveintrodução à noção de centralidade. A segunda seção traz al-guns dos métodos utilizados na determinação do espectro de umgrafo e uma subseção que apresenta os grafos circulantes e seusespectros. Na seção seguinte estudamos isomorfismo de grafos econceitos relacionados. Para mostrar uma aplicação do estudo re-alizado no capítulo, dedicamos a última seção à energia de grafos,conceito que é definido em função dos autovalores da matriz deadjacência e que, surgido no contexto da Química Orgânica, vemdespertando cada vez mais o interesse de matemáticos estudiosos


da Teoria Espectral de Grafos.

2.2 Polinômio característico e espectro de um grafo

Definição 2.1. Seja G = G(V,E) um grafo com n vértices.A matriz de adjacência A(G) de G é a matriz quadrada deordem n cujas entradas são

aij =

{1, se {vi, vj} ∈ E para vi, vj ∈ V ;

0, nos outros casos.

A(G) é uma matriz real formada por uns e zeros. Sendosimétrica, todos os seus autovalores são reais. Como o traço deA(G) é zero então seus autovalores somam zero.

Definição 2.2. O polinômio característico da matriz de adja-cência A(G) de um grafo G, ou seja, det(λI −A(G)), é denomi-nado polinômio característico de G e denotado por pG(λ) ; λé dito um autovalor do grafo G quando λ é uma raiz de pG(λ).Se A(G) possui s autovalores distintos λ1 > . . . > λs com multi-plicidades iguais, respectivamente, a m(λ1), . . . ,m(λs), o espec-tro do grafo G, denotado spect(G), é definido como a matriz2× s, onde a primeira linha é constituída pelos autovalores dis-tintos de A(G) dispostos em ordem decrescente e a segunda, pelassuas respectivas multiplicidades algébricas. Ou seja, escrevemos

spect(G) =

[λ1 · · · λs

m(λ1) · · · m(λs)

].

O maior autovalor de G é denominado índice de G e denotadopor ind(G).

2.2 Polinômio característico e espectro de um grafo 29

Figura 15 – Grafo do Exemplo 2.1.

Exemplo 2.1. Seja G o grafo da Figura 15. Sua matriz deadjacência é

A(G) =

0 1 0 1 1

1 0 1 0 1

0 1 0 0 0

1 0 0 0 1

1 1 0 1 0

.

Seu polinômio característico é pG(λ) = λ5 − 6λ3 − 4λ2 + 3λ+ 2

e seu espectro é

spect(G) =

[2, 6412 0, 7237 −0, 5892 −1 −1, 7757

1 1 1 1 1

].

Portanto ind(G) = 2, 6412.

Devemos notar que a soma das entradas de cada linhada matriz de adjacência de um grafo é igual ao grau do vérticecorrespondente.

A proposição a seguir é um primeiro exemplo de comopropriedades estruturais de grafos são descritas por propriedadesalgébricas de matrizes associadas a eles.


Proposição 2.1. Seja G um grafo com n vértices e m arestase seja

pG(λ) = λn + a1λn−1 + a2λ

n−2 + . . .+ an−1λ+ an

o polinômio característico de G. Então os coeficientes de pG(λ)

satisfazem:

(i) a1 = 0;

(ii) a2 = −m;

(iii) a3 = −2t, onde t é o número de triângulos no grafo.

Demonstração: Da teoria de matrizes ([52]) temos que, para cadai, 1 ≤ i ≤ s, a soma dos menores principais de A(G) com i

linhas e i colunas é igual a (−1)iai (um menor principal deA(G) com i linhas e i colunas é o determinante de qualquersubmatriz principal com i linhas e i colunas de A(G), ouseja, de qualquer matriz obtida de A(G) pela retirada de umsubconjunto de n− i linhas e do correspondente subconjunto decolunas).

i) Como a diagonal de A(G) é formada por zeros entãotodos os seus menores principais com 1 linha e 1 coluna são iguaisa zero, de onde segue que a1 = 0.

ii) Qualquer menor principal de A(G) com 2 linhas e2 colunas e que tenha entradas não-nulas é necessariamente daforma ∣∣∣∣∣ 0 1

1 0

∣∣∣∣∣ .

2.2 Polinômio característico e espectro de um grafo 31

Como cada menor principal destes vale −1 e existe um deles paracada par de vértices adjacentes temos que

(−1)2a2 = (−1).|E| = (−1)m.

Logo, a2 = −m, onde m é o número de arestas de G.

iii) Existem apenas três possibilidades para submatrizesprincipais não nulas de A(G) com 3 linhas e 3 colunas; seusdeterminantes são:∣∣∣∣∣∣∣

0 1 0

1 0 0

0 0 0

∣∣∣∣∣∣∣,∣∣∣∣∣∣∣0 1 1

1 0 0

1 0 0

∣∣∣∣∣∣∣ e

∣∣∣∣∣∣∣0 1 1

1 0 1

1 1 0

∣∣∣∣∣∣∣.Destes, o único não nulo é o último, cujo valor é 2, e que cor-responde a três vértices mutuamente adjacentes, ou seja, umtriângulo. Logo (−1)3a3 = 2× t, onde t é o número de triângulosde G. Assim, a3 = −2t, como queríamos .

Proposição 2.2. O número de cadeias de comprimento l li-gando o vértice vi ao vértice vj em um grafo G é dado pelaentrada de ordem i× j da matriz Al , onde A = A(G) é a matrizde adjacência de G .

Demonstração: (Por indução em l) O resultado é verdadeiro paral = 1 pois A1 = A . Suponhamos o resultado verdadeiro paral = L . Mas existem tantas cadeias de comprimento L+1 ligandovi a vj quantas são as cadeias de comprimento L ligando vi avértices vh adjacentes a vj . Assim, o número de tais cadeias édado por ∑

{vh,vj}∈E

(AL)ih =n∑

h=1

(AL)ihAhj = (AL+1)ij .


Logo o número de cadeias de comprimento L+1 ligando vi a vj

é (AL+1)ij . A conclusão segue por indução.

O resultado acima fornece uma relação entre o númerode cadeias fechadas de um grafo e as somas de potências de seusautovalores, como se vê no seguinte resultado.

Corolário 2.1. Seja G um grafo com n vértices e m arestas esejam λ1, . . . , λn os seus autovalores. Então:(i) se Tl é o número total de cadeias fechadas de comprimento l

em G então Tl = tr(Al) =∑s

i=1 λli. Em particular:

(ii) a soma dos quadrados dos autovalores é duas vezes o númerode arestas, ou seja, T2 = tr(A2) = 2m;(iii) se G é um grafo regular de grau k então T2 =

∑ni=1 λ

2i =

kn , pois kn = 2m;(iv) a soma dos cubos dos autovalores é seis vezes o número t

de triângulos, ou seja, T3 = tr(A3) = 6t.

Figura 16 – Grafos com mesmo p(λ) e ciclos diferentes.

Vemos então que o espectro de um grafo determina onúmero de seus vértices, de suas arestas e de seus triângulos. Noentanto, este fato não pode ser generalizado, ou seja, nem sempreo número de ciclos de comprimento r (r ≥ 4) são determinadosem função de tr(Ar). Os dois grafos da Figura 16 comprovamisto: embora tenham o mesmo polinômio característico, a saber,

2.3 Alguns resultados e aplicações 33

p(λ) = λ5−4λ3, o grafo da direita tem um ciclo de comprimento4 e o outro não tem ciclos.

2.3 Alguns resultados e aplicações

Como aplicação do estudo realizado, vejamos uma situ-ação simples onde se usa a Proposição 2.2.

Exemplo 2.2. Consideremos o problema de construir um metrônuma grande cidade.

São escolhidos n locais estratégicos, digamos v1, . . . , vn,que devem possuir estações de metrô. Estas estações, juntamentecom as linhas de metrô definidas para fazerem as interligaçõesentre elas, formam uma malha ou rede. Esta rede pode ser repre-sentada por um grafo, cujos vértices são as estações e as arestasindicam as linhas de metrô que as interligam.

A questão que se coloca é: escolhendo-se duas estaçõesquaisquer, sempre existe um caminho na rede que as ligue? Parauma resposta positiva, é necessário que o grafo seja conexo. SeA é a matriz de adjacência do grafo basta então que A + A2 +

. . .+An−1 não tenha nenhuma entrada nula.

Por exemplo, se n = 10 e a matriz do grafo que repre-senta a rede é


A =

0 1 0 0 0 0 0 0 0 0

1 0 1 0 0 0 0 0 0 0

0 1 0 1 0 0 1 0 0 0

0 0 1 0 1 0 0 0 0 0

0 0 0 1 0 1 0 0 1 0

0 0 0 0 1 0 0 0 0 0

0 0 1 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0 0 0

0 0 0 0 1 0 0 0 0 1

0 0 0 0 0 0 0 0 1 0

então A+A2 + . . .+A9 é a matriz

31 119 87 133 46 46 114 27 55 9

119 118 366 133 234 46 114 114 55 55

87 366 278 467 188 188 366 87 234 46

133 133 467 200 421 96 133 133 124 124

46 234 188 421 232 233 234 46 311 78

46 46 188 96 233 58 46 46 78 78

114 114 366 133 234 46 118 119 55 55

27 114 87 133 46 46 119 31 55 9

55 55 234 124 311 78 55 55 108 109

9 55 46 124 78 78 55 9 109 30

,

que tem todas as entradas diferentes de zero, garantindo a cone-xidade do grafo.

O Teorema a seguir, conhecido como Teorema de en-trelaçamento para a matriz de adjacência, nos dá uma relaçãoentre os autovalores de um grafo e os autovalores de um subgrafo


induzido - em particular, do subgrafo obtido pela retirada de umvértice. A prova decorre de um teorema geral de matrizes cujaprova pode ser encontrada no Apêndice (Teorema 7.1).

Teorema 2.1. Seja G = G(V,E) um grafo com n vértices eautovalores λ1 ≥ λ2 ≥ . . . ≥ λn e seja H = H(V ′, E′) umsubgrafo induzido de G com m vértices. Se os autovalores de H

são µ1 ≥ µ2 ≥ . . . ≥ µm então, para cada i, 1 ≤ i ≤ m valeλn−m+i ≤ µi ≤ λi. Em particular, se v ∈ V e V ′ = V \ {v}então λi+1 ≤ µi ≤ λi para cada i, 1 ≤ i ≤ n− 1.

Demonstração: Escolhamos V = {1, . . . , n} e V ′ = {1, . . . ,m}.Então a matriz de adjacência A(H) de H é uma submatriz prin-cipal de A, pois é obtida desta pela retirada das n−m últimaslinhas e das correspondentes colunas. Portanto o resultado seguedo Corolário do Teorema 7.1 (ver Apêndice).

Quando usamos grafos para modelar redes, uma questãorelevante é destacar os vértices mais importantes naquele con-texto, isto é, os vértices mais influentes na rede. Esta influênciaou importância do vértice depende do tipo de relação modelada,representada pelas arestas do grafo, e é avaliada por meio de me-didas de centralidade. Dentre as mais conhecidas estão a centra-lidade de grau (degree centrality), também chamada centralidadede informação, [38], a centralidade de intermediação (betwennesscentrality), [37], e a centralidade de proximidade (closeness cen-trality), [74]. Todas estas são medidas não espectrais.

Em 1987, Bonacich [13] propôs uma medida de centra-lidade a partir de um autovetor associado ao índice do grafo.


Antes de apresentar a definição vamos relembrar algunsresultados de Álgebra Linear.

Definição 2.3. O raio espectral de um grafo G, denotadopor ρ(G), é o número real não negativo ρ(G) = maxi |λi|, ondeλ1, . . . , λn são os autovalores de G.

Portanto, o raio espectral de um grafo é o raio do in-tervalo de centro na origem que contém todos os autovalores deG.

Seja G um grafo conexo. O Teorema de Perron-Frobenius,cuja prova pode ser encontrada no Apêndice (Teorema 7.4),garante que o raio espectral é o índice do grafo, pois grafosconexos possuem matrizes de adjacência irredutíveis (Proposição7.4 do Apêndice). E também que ρ(G) é positivo e tem multipli-cidade algébrica igual a 1. Portanto, a multiplicidade geométricaé também 1, isto é, o espaço gerado pelos autovetores associa-dos ao índice é unidimensional. O Teorema de Perron-Frobeniusgarante ainda que existe um autovetor associado ao índice comtodas as coordenadas positivas. Isto permite introduzir uma novamedida de centralidade de vértice para um grafo.

Definição 2.4. A centralidade de autovetor do vértice vi dografo G é a i-ésima coordenada xi do autovetor unitário positivox = [x1 . . . xn]

T associado ao índice λ1 do grafo, ou seja, é onúmero

xi =1

λ1

n∑j=1

aijxj ,

onde os aij são as entradas da sua matriz de adjacência.


Note-se que, como a multiplicidade do raio espectral é1, qualquer autovetor não negativo fornece a mesma ordenaçãopara os vértices.

Exemplo 2.3. Considere o grafo da Figura 15. Como já vimosno Exemplo 2.1, o índice deste grafo é 2, 6412. Um autovetorassociado a ele é x = [0, 5370, 0, 4747, 0, 1797, 0, 4066, 0, 5370].Embora os vértices v1, v2 e v5 tenham o mesmo grau (e portantoa mesma centralidade de grau) os vértices v1 e v5 têm centrali-dade de autovetor maior do que a do vértice v2.

Em muitas aplicações essa medida de centralidade devértice tem se mostrado mais adequada que as outras medidascitadas anteriormente. Isto se deve ao fato de a centralidade deautovetor de um vértice considerar, além do grau do própriovértice, também o grau de seus vizinhos, dos vizinhos dos seusvizinhos, e assim por diante. Esta afirmação é decorrência doMétodo da Potência (ver [73]) aplicado à matriz de adjacênciaA (o método pode ser usado para esta matriz pois ela é diag-onalizável e λ1 é o raio espectral). Verifica-se facilmente que amatriz A multiplicada pelo vetor 1=[1 . . . 1]T fornece o vetor degraus dos vértices, que A2 · 1 fornece o vetor da soma dos grausdos vizinhos de cada vértice, e assim por diante. O Método daPotência diz que a sequência (An ·1)n converge para um autove-tor associado a λ1 quando n→∞.

A centralidade de autovetor é, portanto, a medida maisconveniente quando se estuda propagação de um fenômeno numarede, como por exemplo, no estudo de expansão de epidemias.Em [9] e [14] a centralidade de autovetor é usada para estu-dar AIDS. Em [42], esta centralidade é aplicada a uma rede detransportes.


As duas próximas proposições relacionam os autovaloresde um grafo e alguns dos parâmetros apresentados no primeirocapítulo. Escrevemos Mn para indicar o conjunto de todas asmatrizes quadradas de ordem n.

Proposição 2.3. Se G é um grafo conexo então o número deautovalores distintos de A é no mínimo diam(G) + 1.

Demonstração: Sejam λ1, λ2, · · · , λt os autovalores distintos deG. Como A é uma matriz simétrica e real, seu polinômio mínimotem grau t e portanto

(A− λ1I)(A− λ2I) · · · (A− λtI) = O .

Logo At é uma combinação linear de I, A,A2, · · · , At−1 . Supo-nhamos t ≤ diam(G) e tomemos u e v dois vértices de G tais qued(u, v) = t . Então (Ai)uv = 0 para todo i com 0 ≤ i ≤ t − 1 e(At)uv > 0, o que é uma contradição. Portanto t ≥ diam(G)+1 .

Proposição 2.4. Se G é um grafo com maior autovalor λ1 então

d ≤ λ1 ≤ △ .

Demonstração: Seja G um grafo com n vértices. Sendo A a ma-triz de adjacência de G e λ1 seu maior autovalor, o Princípio deRayleigh (aqui, Corolário da Proposição 7.2) garante que

λ1 = maxx̸=0

xTAx

xTx.

Seja 1 = [1, · · · , 1]T . Então temos que

1TA11T1

=1

n

n∑i=1

(

n∑j=1

aij) =1

n

n∑i=1

d(vi) = d


e, portanto, d ≤ λ1. Agora, a função N definida por

N(M) = max1≤i≤n

n∑j=1

mij ,

para M = (mij) em Mn, define uma norma sobre Mn. Notar queN(A) = △. Se λ é um autovalor de A, o Teorema de Perron-Frobenius (Teorema 7.4) afirma que |λ| ≤ λ1; além disso, existepelo menos um autovalor λ tal que |λ| = λ1. Se Ax = λx parax ̸= 0 e se |λ| = λ1, consideremos a matriz X de Mn cujascolunas são todas iguais ao autovetor x e observemos que AX =

λX. Então

|λ|N(X) = N(λX) = N(AX) ≤ N(A)N(X)

e daí |λ| = λ1 ≤ N(A) = △ .

Na próxima proposição, vemos como técnicas de otimiza-ção são usadas para estabelecer um limite superior para o índicede um grafo. Técnicas de otimização combinatória são usadas emsoftwares elaborados para resolver problemas em grafos, comopor exemplo, o Autographix System. Este software, criado porPierre Hansen e Gilles Caporossi, tem por objetivo gerar conjec-turas, fazer provas semiautomáticas e analisar e descrever classesde grafos [18]. O problema de encontrar um grafo com determi-nadas propriedades é transformado em um problema de otimiza-ção com a função-objetivo envolvendo um ou mais invariantes e,possivelmente, com algumas restrições.

Proposição 2.5. Se G é um grafo com m arestas, n vértices eautovalores λ1, . . . , λn então

λ1 ≤√2m(1− 1

n

).


Demonstração: Pelo Corolário 2.1 temos que λ1+λ2+ . . .+λn =

0 e λ21 + λ2

2 + . . . + λ2n = 2m. Sejam f , g e h funções de

Rn em R definidas por f(x1, . . . , xn) = x1, g(x1, . . . , xn) =

x1 + x2 + . . .+ xn e h(x1, . . . , xn) = x21 + x2

2 + . . .+ x2n.

Consideremos o seguinte problema de maximização comrestrições de igualdade: encontrar

max f(x1, . . . , xn)

sujeito às restrições

g(x1 . . . xn) = 0 e h(x1 . . . xn) = 2m.

Definimos então a Lagrangeana

L(x1, . . . , xn, k1, k2) = x1 − k1(x1 + x2 + . . .+ xn)+

−k2(x21 + x2

2 + . . .+ x2n − 2m)

e, resolvendo por multiplicadores de Lagrange, obtemos:

∂L

∂x1= 1− k1 − 2k2x1 = 0; (2.3.1)

∂L

∂xi= −k1 − 2k2xi = 0, para todo i, 2 ≤ i ≤ n; (2.3.2)

x1 + x2 + . . .+ xn = 0; (2.3.3)

x21 + x2

2 + . . .+ x2n = 2m. (2.3.4)

Temos que k2 ̸= 0, pois, caso contrário, k1 seria simultaneamenteigual a 0 e 1. Daí, segue de (2.3.2) que, para cada i, 2 ≤ i ≤ n,

xi =−k12k2

. De (2.3.3), segue então que x1 +(n− 1)(−k12k2

)= 0 .

Logo, x1 = −(n− 1)(−k12k2

), e portanto,

x1 = (n− 1)( k12k2

). (2.3.5)

Substituindo (2.3.5) em (2.3.4), obtemos

(n−1)2( k12k2

)2+(n−1)

( k1−2k2

)2= (n−1)

( k12k2

)2(n−1+1) =

= n(n− 1)( k12k2

)2= 2m.

Segue daí quek12k2

=

√2m

n(n− 1). Voltando a (2.3.5), obtemos

x1 = (n− 1)( k12k2

)= (n− 1)

√2m

n(n− 1)=

√(n− 1)2

2m

n(n− 1)=

√2m(1− 1

n

).

2.4 O espectro de certos tipos de grafos

A determinação do espectro de um grafo com mais doque 4 vértices pelo cálculo direto das raízes de seu polinômiocaracterístico é realizada para grafos particulares com o auxíliode softwares de computação algébrica. Existem alguns softwaresespecíficos para o trabalho com grafos. Um deles é o NewGraph1

de Dragan Stevanić, disponível a partir deSpectral Graph Theory Home Page,

cujo sítio http://www.sgt.pep.ufrj.br/index.php é mantido peloPrograma de Pesquisa Operacional da COPPE-UFRJ para pro-mover o estudo e a divulgação da Teoria Espectral de Grafos.1 Último acesso em 26 de dezembro de 2013. Usado neste trabalho, este

software calcula diversos invariantes a partir do desenho do grafo.


Voltando ao problema de determinação do espectro de um grafo,a abordagem teórica direta da questão é bastante árdua e forneceàs vezes resultados difíceis de serem manipulados. Alternativa-mente, alguns teoremas determinam o espectro de grafos obtidosa partir de outros por operações como o complementar, a união,etc.. Outros resultados fornecem apenas informações sobre al-guns dos autovalores. E há aqueles que fornecem diretamente oespectro de certos tipos especiais de grafos por meio de algumartifício algébrico. No cômputo geral, são conhecidos os espectrosapenas de algumas poucas classes de grafos.

Proposição 2.6. Se o grafo G é a união de dois grafos G1 eG2 então pG(λ) = pG1(λ).pG2(λ). Em particular, se G1, G2, . . .,Gr são as componentes conexas de um grafo G então pG(λ) =

pG1(λ)pG2(λ) . . . pGr (λ).

Demonstração: Se Ai é a matriz de adjacência de Gi (i = 1, 2),então a matriz de adjacência A(G) de G é da forma[

A1 O

O A2

].

Pelo teorema de expansão de Laplace para determinantes [52],obtemos pG(λ) = pG1(λ).pG2(λ).

No próximo resultado, merece destaque a técnica de uti-lizar um especial autovetor para garantir que k é autovalor dequalquer grafo k-regular.

Proposição 2.7. Seja G um grafo regular de grau k. Então:

(i) k é um autovalor de G;

2.4 O espectro de certos tipos de grafos 43

(ii) G é um grafo conexo se e somente se a multiplicidade de k

é 1;

(iii) qualquer autovalor λ de G satisfaz |λ| ≤ k.

Demonstração: (i) Seja 1 o vetor coluna [1 1 . . . 1]T . Como asoma das entradas de cada linha da matriz de adjacência A =

A(G) de G é k, o grau de cada vértice, temos que A1 = k1 , ouseja, k é um autovalor de G .(ii) Seja x = [x1x2 . . . xn]

T um autovetor associado ao autovalork de G e suponhamos que xj é uma entrada de x com valorabsoluto máximo. Temos que (Ax)j =

∑xi , onde o somatório é

considerado sobre os k vértices vi que são adjacentes a vj . Logo∑xi = kxj . Daí temos que, para cada l tal que vl é adjacente

a vj ,

|xj |+ (k − 1)|xj | = |∑

xi| ≤∑|xi| ≤ |xl|+ (k − 1)|xj | .

Isto nos fornece |xj | ≤ |xl| e, portanto, xl = xj para todos estesk vértices. Como G é conexo, podemos prosseguir sucessivamentedesta maneira até mostrar que todas as entradas de x são iguais.Então x é múltiplo de 1 e o autoespaço associado ao autovalork tem dimensão 1 .

Reciprocamente, supondo que G é desconexo, sejam G1,G2, ..., Gm as suas componentes conexas . Como cada uma é umgrafo conexo k-regular então k é um autovalor de multiplicidade1 para cada Gi. Mas como pG(λ) = pG1(λ).pG2(λ) . . . pGm(λ)

(Proposição 2.6), segue que k é um autovalor de G de multipli-cidade m > 1. Logo a asserção está provada.(iii) Seja y um vetor não nulo de G associado a um autovalor λ

de G e seja yj uma entrada de y com valor absoluto máximo.


Como em (ii), temos∑

yi = λyj e |λ||yj | = |∑

yi| ≤ k|yj | .Logo, |λ| ≤ k .

De modo geral, não conhecemos todo o espectro de umgrafo k-regular. Mas, dado que conhecemos seus autovalores,podemos determinar os autovalores do seu grafo complementar.

Proposição 2.8. Seja G um grafo k-regular com n vértices eautovalores k, λ2, λ3,. . ., λn. Então os autovalores de G sãon − k − 1, −1 − λ2, −1 − λ3, . . ., −1 − λn, respectivamenteassociados aos mesmos autovetores de G.

Demonstração: É fácil verificar que a matriz de adjacência A(G)

de G satisfaz

A(G) = J − I −A(G),

onde J é a matriz quadrada de ordem n em que todas as entradassão iguais a 1. Seja {1,u2, . . . ,un} uma base ortogonal de au-tovetores de A(G) associados, respectivamente, aos autovaloresk, λ2, . . . , λn. Como A(G).1 = k1 então

A(G).1 = (J − I −A(G)).1 = (n− k − 1)1,

e portanto, 1 é autovetor de G associado ao autovalor n− k− 1.Além disso, para cada i, 2 ≤ i ≤ n,

A(G).ui = (J − I −A(G)).ui = −ui − λiui = (−1− λi)ui,

de onde segue que ui é autovetor de G associado ao autovalor−1− λi.


Exemplo 2.4. Se G é o grafo sem arestas com n vértices entãopG(λ) = λn e, portanto,

spect(G) =

[0

n

].

Exemplo 2.5. Kn, o grafo completo com n vértices, é o comple-mentar do grafo do Exemplo anterior, que é 0-regular. Tem-seentão que pKn(λ) = (λ− n+ 1)(λ+ 1)

(n−1) e

spect(Kn) =

[n− 1 −11 n− 1

].

Exemplo 2.6. Se G é o grafo formado pela união de s cópias deK2 então G é 1-regular e tem 2s vértices. Como vimos, pK2(λ) =

λ2− 1 e, portanto, pela Proposição 2.6, pG(λ) = (λ2 − 1)s. Logo

spect(G) =

[1 −1s s

].

Figura 17 – O hiperoctaedro H5.

O grafo complementar de G é chamado hiperoctaedro(ou “cocktail party graph“) e denotado por Hs (ver Figura 17).


Pela Proposição 2.8, temos que

spect(G) =

[2s− 2 0 −2

1 s s− 1

].

No Exemplo 2.10 veremos uma outra forma de calcular o espectrodeste grafo.

Exemplo 2.7. Seja G um grafo bipartido cujo conjunto de vér-tices é particionado em dois subconjuntos disjuntos V1 e V2, com|V1| = k1 e |V2| = k2. Se rotulamos primeiramente os vértices deV1 e só depois os de V2, conseguimos que a matriz de adjacênciatenha a forma

A(G) =

[O B

BT O

],

onde B é uma matriz k1 × k2. Afirmamos que λ é autovalorde G se e somente se −λ é autovalor de G. De fato, tomemosum autovetor x = [x1 . . . xk1 y1 . . . yk2 ]

T de A(G) associado aoautovalor λ de G. Vamos mostrar que −λ é também autovalorde G, exibindo um de seus autovetores associados, a saber, x̃ =

[x1 . . . xk1−y1 . . . −yk2

]T . Realmente, como (A(G)x)T= λxT

entãoB

y1...

yk2

BT

x1

...xk1

= [λx1 . . . λxk1 λy1 . . . λyk2 ].

Por outro lado,

(A(G)x̃)T=

B−y1...−yk2

BT

x1

...xk1

=

= [−λx1 . . . − λxk1 λy1 . . . λyk2 ] =

= (−λ) [x1 . . . xk1 − y1 . . . − yk2 ] = (−λ)x̃T .


2.4.1 Grafos circulantes e seus espectros

Os grafos circulantes formam uma subclasse da classedos grafos regulares. Para eles é possível dar uma descrição com-pleta do espectro.

Definição 2.5. Consideremos n ∈ N∗ e representemos o aneldos inteiros módulo n por Zn = {0, 1, 2, . . . , n−1}. Dados l ∈ N∗

e inteiros k1 < k2 < . . . < kl ∈ {1, 2, . . . , ⌊n2 ⌋}, dizemos queum grafo G com conjunto de vértices V = {0, 1, . . . , n − 1} écirculante quando os vértices adjacentes a cada vértice i sãoexatamente i+kr e i−kr reduzidos módulo n, para r = 1, 2, . . . , l.Neste caso, escrevemos G = Ci(n, k1, . . . , kl).

Figura 18 – Ci(6, 2), Ci(6, 1, 3), Ci(6, 1, 2) e Ci(6, 2, 3).

Assim, por exemplo, para n = 5, Ci(5, 1) = Ci(5, 2) =

C5. Para n = 6, Ci(6, 1) = C6 e Ci(6, 1, 2, 3) = K6. Na Figura18 ilustramos os outros grafos circulantes com n = 6 vértices. Demodo geral, Ci(n, 1) = Cn, para todo inteiro n ≥ 3 e Ci(n, 1, 2, . . . , ⌊n2 ⌋) =Kn, para cada n ≥ 2.

Dado G = Ci(n, k1, . . . , kl) um grafo circulante, onden, l, k1, . . . , kl são escolhidos como acima, temos que a matrizde adjacência A = [aij ] de G satisfaz ai,j = a0,j−i, onde osíndices pertencem a {0, 1, 2, . . . , n − 1} e são reduzidos módulo


n. De fato, o vértice 0 é adjacente ao vértice j − i(mod n) emG⇔ j−i = kr(mod n) ou j−i = −kr(mod n), para algum kr dalista k1, . . . , kl ⇔ j = i+kr(mod n) ou j = i−kr(mod n), ou seja,o vértice i é adjacente ao vértice j em G. A é o que se chamauma matriz circulante. Portanto, a matriz de adjacência dequalquer grafo circulante é determinada por sua primeira linha,sendo cada linha i a seguir, obtida da primeira pela permutaçãocíclica de i posições.

A teoria de matrizes circulantes afirma que: se

[0, a1, a2, . . . , an−1]

é a primeira linha de uma matriz circulante C então, considerando-se o polinômio q(λ) = a1λ+a2λ

2+. . .+an−1λn−1, os autovalores

de C são dados exatamente por q(ω) =∑n−1

j=1 ajωj , para cada

raiz n-ésima da unidade ω, (ver [6], por exemplo).

Pelo que foi visto acima, a primeira linha da matriz deadjacência de G = Ci(n; k1, k2, . . . , kl), que corresponde aovértice 0, possui 1 nas posições k1, k2, . . . , kl, n − k1, n −k2, . . . , n− kl e 0 nas posições restantes.

Daí, se fazemos ω = e2πin , os autovalores de G podem

ser escritos como

λj =∑{ωjk : 1 ≤ k ≤ n− 1, k = kr, n− kr para r = 1, 2, . . . , l},

onde j = 0, 1, . . . , n− 1.

Para j = 0, obtemos assim

λ0 =l∑

r=1

ω0.kr +l∑

r=1

ω0.(n−kr) = 2l.


Fixemos, por um momento, j ∈ N tal que 1 ≤ j ≤ n−1.

Temos que

λj =l∑

r=1

wjkr +l∑

r=1

wj(n−kr) =l∑

r=1

e2πin jkr +

l∑r=1

e2πin j(n−kr) =

=

l∑r=1

(coskr

2πj

n+ isenkr

2πj

n

)+

+l∑

r=1

(cos(n− kr)

2πj

n+ isen(n− kr)

2πj

n

)=

=l∑

r=1

(coskr

2πj

n+ cos(n− kr)

2πj

n

)+

+il∑

r=1

(senkr

2πj

n+ sen(n− kr)

2πj

n

).

Usando então as relações trigonométricas

senk2π

n= −sen(n− k)

2π

ne cosk

2π

n= cos(n− k)

2π

n,

obtemosl∑

r=1

(senkr

2πj

n+ sen(n− kr)

2πj

n

)= 0

el∑

r=1

(coskr

2πj

n+ cos(n− kr)

2πj

n

)=

l∑r=1

2coskr2πj

n.

Concluímos que os autovalores do grafo G = Ci(n, k1, k2, . . . , kl)

são portanto, da forma

λj =l∑

r=1

2coskr2πj

n, para j = 1, . . . , n− 1.


Exemplo 2.8. O ciclo Cn.

Fixado um inteiro n ≥ 2, a matriz de adjacência deCn = Ci(n; 1) é a matriz circulante, cuja primeira linha é[

0 1 0 . . . 0 1].

Considerando então o polinômio q(x) = x+ x(n−1), temos queλ0 = q(1) = 1+1 = 2 é autovalor de Cn, como era de se esperar(vide Proposição 2.7). Expressando as outras n-ésimas raízesda unidade como potências de ω = e2πi/n, obtemos os demaisautovalores de Cn dados por

λj = q(ωj) = ωj + ωj(n−1),

para cada j, 0 ≤ j ≤ n− 1. Como vimos acima e usando somasde cossenos, obtemos

λj = cos(jπn

)+ cos

(j(n− 1)π

n

)=

= 2cos(2jπ

2

)cos(2j(n− 2)π

2n

)=

= 2cos(jπ)cos(jπ−2jπ

n

)= 2(cos(jπ))2cos

(2jπn

)= 2cos

(2jπn

),

para cada j, 0 ≤ j ≤ n − 1. Mas estes números não são to-dos distintos. Levando-se em conta as coincidências, a descriçãocompleta do espectro é: para n ímpar,

spect(Cn) =

[2 2cos(2π/n) . . . 2cos(n− 1)π/n

1 2 . . . 2

],

e para n par,

spect(Cn) =

[2 2cos(2π/n) . . . 2cos(n− 2)π/n −21 2 . . . 2 1

].


Exemplo 2.9. O grafo “Möbius Ladder”.

Dado um inteiro h ≥ 2, o grafo Mh = Ci(2h; 1, h) échamado Möbius Ladder (literalmente, “escada de Möbius”).Mh é um grafo 3-regular com 2h vértices.

Figura 19 – M5 (Möbius Ladder com 10 vértices)

A matriz de adjacência A(Mh) de Mh é portanto a ma-triz circulante de ordem 2h cuja primeira linha é dada por[

0 1 0 . . . 1︸︷︷︸entrada 1,h

. . . 0 1].

Considerando então o polinômio q(x) = x+ xh + x2h−1 , temosque λ0 = q(1) = 1+1+1 = 3 é autovalor de Mh. Além disso, seexpressamos as outras raízes 2h-ésimas da unidade como potên-cias de ω = e2πi/2h, os restantes autovalores de Mh são dadospor

λk = q(ωk) = ωk + ωkh + ωk(2h−1),

para cada k, 1 ≤ k ≤ 2h−1. Desenvolvendo a partir do resultadogeral obtido acima, temos, para cada k, 1 ≤ k ≤ 2h− 1 ,

λk = cos(2kπ

2h

)+ cos

(2khπ2h

)+ cos

(2k(2h− 1)π

2h

)=

= cos(kπ

h

)+ cos(kπ) + cos

(2kπ − kπ

h

)=

= cos(kπ

h

)+ cos(kπ) + cos

(kπh

)= 2cos

(kπh

)+ (−1)k .

Exemplo 2.10. O hiperoctaedro ou “cocktail party graph” (verExemplo 2.6).

O hiperoctaedro Hs é um grafo com 2s vértices no qualcada vértice vi é adjacente a todos os outros, menos ao vi+s.Ou seja, Hs é o grafo complementar de Ci(2s; s), sendo por-tanto igual a Ci(2s; 1, . . . , s − 1). Usando o mesmo raciocíniodos exemplos anteriores, obtemos o espectro de Hs, já calculadono Exemplo 2.6.

2.5 Isomorfismo de Grafos

Definição 2.6. G1 e G2 são ditos grafos isomorfos quandoexiste uma correspondência biunívoca entre seus conjuntos devértices de modo que as adjacências sejam preservadas. Nestecaso, a bijeção é chamada um isomorfismo.

Exemplo 2.11. Os grafos da Figura 20 são isomorfos, coma bijeção entre os conjuntos de vértices dada por f(vi) = ui,i = 1, . . . , 8.

Assim dois grafos G1 e G2 são isomorfos quando pode-mos obter um do outro através de uma permutação das rotu-lações de seus vértices. Isto significa que A(G1) e A(G2) são ma-trizes semelhantes, ou seja, que existe uma matriz de permutaçãoP (que é uma matriz ortogonal) tal que PTA(G1)P = A(G2) .Isomorfismos permitem distinguir as propriedades inerentes à es-trutura própria do grafo (os chamados invariantes de grafos)

2.5 Isomorfismo de Grafos 53

Figura 20 – G1 e G2 são grafos isomorfos.

daquelas que dependem da sua representação, como o desenho ea rotulação dos vértices.

Definição 2.7. G1 e G2 são ditos grafos coespectrais quandotêm os mesmos autovalores com as mesmas multiplicidades, istoé, quando spect(G1) = spect(G2) .

Se dois grafos são isomorfos eles têm o mesmo espectro.A recíproca dessa afirmação não é verdadeira em geral, comoilustra o exemplo a seguir:

Figura 21 – G1 e G2 são grafos não isomorfos e coespectrais.

Exemplo 2.12. Os grafos G1 e G2 da Figura 21 são coespectrais

54 A matriz de adjacência

com

pG1(λ) = pG2(λ) = λ6 − 7λ4 − 4λ3 − 7λ2 + 4λ− 1.

Mas não são isomorfos, pois como vemos, G2 tem um vértice degrau 5 e, em G1, o grau máximo é 3.

Definição 2.8. Dizemos que um grafo G é caracterizado peloseu espectro quando os grafos coespectrais com G são isomorfosa G .

O fato de existirem grafos coespectrais não isomorfossignifica que algumas propriedades de grafos não podem ser car-acterizadas pelo espectro. A conexidade e a existência de ciclosde comprimento 4, por exemplo, são propriedades que não de-pendem do espectro dos grafos, como vimos na Figura 16. Ograu dos vértices é também uma propriedade não caracterizadapelo espectro.

Proposição 2.9. Um grafo G possui um único autovalor se esomente se G é totalmente desconexo, ou seja, é um grafo semarestas.

Demonstração: Seja λ autovalor de G com multiplicidade k.Como o traço da matriz de adjacência A(G) de G é zero entãoλ é zero. Logo o polinômio mínimo de A(G) é h(x) = x− λ = x

e daí,

A(G) =

0 0 0 ... 0

0 0 0 ... 0

... ... ... ... ...

0 0 0 ... 0

.

Portanto, G possui k vértices isolados.

2.5 Isomorfismo de Grafos 55

Corolário 2.2. Grafos sem arestas são caracterizados pelo seuespectro.

Proposição 2.10. Se um grafo G tem exatamente dois autova-lores distintos λ1 > λ2, com multiplicidades m1 e m2, respecti-vamente, então G é o grafo regular de grau λ1 formado por m1

cópias de Kλ1+1. Temos ainda que λ2 = −1 e m2 = m1λ1.

Demonstração: Sejam λ1 > λ2 os dois únicos autovalores de umgrafo G com n vértices. Então a matriz de adjacência A = A(G)

de G tem polinômio mínimo h(x) = (x−λ1)(x−λ2) e, portanto,

A2 − (λ1 + λ2)A+ λ1λ2I = O . (2.5.6)

Considerando os elementos da diagonal, temos (A2)kk = −λ1λ2 ,todo k, 1 ≤ k ≤ n . Pela Corolário 2.1, esta relação indica queo número de cadeias fechadas de comprimento dois (arestas)partindo de cada vértice vk é constante e igual a −λ1λ2, ou seja,que G é um grafo (−λ1λ2)-regular. Pela Proposição 2.7 temosque λ1 = −λ1λ2 (o grau é o maior autovalor). Mas λ1 ̸= 0,pois em caso contrário, λ2 = 0, já que tr(A) = 0 = λ1 + λ2,contrariando o fato de que G possui dois autovalores distintos.Portanto, λ2 = −1 e G é um grafo regular de grau λ1. Fixemosum vértice vi de G. Então vi é adjacente a λ1 vértices que sãonecessariamente adjacentes entre si, pois como

(A2)ij = (λ1 + λ2)(A)ij = 0,

para todo vértice vj de G não adjacente a vi, não há vérticesadjacentes àqueles λ1 vértices fora do conjunto de vértices adja-centes a vi. Portanto, estes λ1 + 1 vértices formam uma compo-nente conexa de G que é λ1-regular, ou sejam, formam Kλ1+1.Claramente, as demais componentes também são iguais a Kλ1+1.

Como λ1 tem multiplicidade igual a 1 em cada Kλ1+1

então G é formado por m1 cópias de Kλ1+1. Com o mesmoraciocínio, como λ2 = −1 tem multiplicidade λ1 em cada umadas m1 cópias de Kλ1+1, segue que m2 = λ1m1.

2.6 Energia de grafos

De acordo com a teoria quântica, propriedades de elétrons,átomos e moléculas num estado estacionário, são descritas porfunções de ondas envolvendo massa e energia potencial. Hückelestudou os hidrocarbonetos insaturados, onde a estrutura damolécula pode ser representada por um grafo, como mostra aFigura 22.

Figura 22 – Hidrocarboneto e grafo que o representa.

Os vértices do grafo correspondem aos átomos de car-bono do hidrocarboneto. Dois vértices são adjacentes se, e so-mente se, existe uma ligação entre os átomos de carbono corre-spondentes. Pela teoria de Hückel [53], os autovalores do grafo

2.6 Energia de grafos 57

correspondem aos níveis de energia dos elétrons π. Desse modo, oproblema de determinação de energia de cada orbital molecularé reduzido ao da determinação do espectro do grafo correspon-dente. No estudo dos hidrocarbonetos conjugados insaturadospela Teoria de Hückel, os grafos são sempre conexos, planarese com grau máximo 3 (os vértices correspondem a átomos decarbono com valência no máximo 3); são os chamados grafosmoleculares. Apesar destas restrições, esta classe de grafos ébastante ampla, envolvendo muitos problemas não triviais deTeoria Espectral de Grafos.

Nesta seção de aplicação das propriedades da matriz deadjacência, pretendemos estudar alguns tópicos sobre energia degrafos.

A energia total dos elétrons π é um dos mais conheci-dos conceitos relacionados às características químicas de umamolécula. As pesquisas sobre suas propriedades datam de 1940.Em 1978, I. Gutman introduziu o conceito de energia de umgrafo em [45]. Inicialmente definido para os grafos moleculares, aabordagem matemática da questão vem ganhando cada vez maiscontribuições, como se pode ver comprovar pelo survey [47] de2005, e pelas referências ali contidas.

Definição 2.9. A energia de um grafo G com n vértices é onúmero

E(G) =n∑

i=1

|λi|,

onde λ1, . . . , λn são os autovalores de G.

Exemplo 2.13. Como consequência do Exemplo 2.5 tem-se que

E(Kn) = 2(n− 1).


O cálculo da energia de um grafo depende da determi-nação do seu espectro, o que, como já vimos, não é tarefa fácil.Desde o início do estudo deste conceito, no entanto, estimativasforam feitas para se determinar o “tamanho” desta grandeza,que resultaram no estabelecimento de limites superiores e infe-riores para ela. Vamos em seguida apresentar alguns dos limitesconhecidos para este parâmetro.

2.6.1 Limites para a energia de um grafo

Um dos primeiros (1971) limites estabelecidos para aenergia de um grafo, e um dos mais conhecidos, foi determinadopor McClelland [68] em termos unicamente dos números de vér-tices e de arestas do grafo.

Proposição 2.11. Se G é um grafo com n vértices e m arestasentão

E(G) ≤√2mn. (2.6.7)

Demonstração: Seja G um grafo com n vértices, m arestas eautovalores λ1, . . . , λn. Pela desigualdade de Cauchy-Schwarz epelo Corolário 2.1(ii), temos

(E(G))2 = (

n∑i=1

|λi|)2 ≤n∑

i=1

λi2.

n∑i=1

1 = n

n∑i=1

λi2 = 2nm.

Logo E(G) ≤√2mn.

A igualdade vale em (2.6.7) se e somente se os valoresabsolutos de todos os autovalores do grafo G são iguais, ou seja,quando G é formado por cópias de K1 ou cópias de K2.


No próximo teorema são estabelecidos limites para E(G)

que dependem somente do número de arestas do grafo.

Teorema 2.2 ([18]). Se G é um grafo com m arestas então

2√m ≤ E(G) ≤ 2m.

E ainda, E(G) = 2√m se e somente se G é um grafo bipartido

completo mais uma quantidade arbitrária de vértices isolados, eE(G) = 2m se e somente se G consiste de m arestas isoladasmais vértices isolados.

Demonstração: Seja G um grafo com m arestas e autovaloresλ1, . . . , λn. Da Definição 2.9 segue que

[E(G)]2 =n∑

i=1

|λi|2 + 2n∑

i<j

|λi||λj |. (2.6.8)

Ora, é possível provar (Exercício 1 deste Capítulo) que

n∑i<j

λiλj = −m.

Em vista disto,n∑

i<j

|λi||λj | ≥ |n∑

i<j

λiλj | = m. (2.6.9)

Daí e do Corolário 2.1(ii), segue de 2.6.8 que

[E(G)]2 ≥ 4m,

ou seja,E(G) ≥ 2

√m.

Da desigualdade (2.6.9), vemos que E(G) = 2√m ocorre exata-

mente quando o grafo G tem exatamente um autovalor positivo


e um autovalor negativo. Mostra-se que este é o caso exatamentequando uma componente de G é um grafo bipartido completo eas outras componentes são vértices isolados (ver [23]).

Consideremos agora que G não tenha vértices isolados.Neste caso, n ≤ 2m e daí

√2mn ≤

√4m2 = 2m. (2.6.10)

Levando em conta a desigualdade (2.6.7), obtemos

E(G) ≤ 2m. (2.6.11)

Os autovalores de mK2 são +1 e −1, ambos com mul-tiplicidade m, e portanto, os valores absolutos de todos os au-tovalores são iguais. Logo, para G = mK2 temos a igualdadeem (2.6.7) e (2.6.10) e, portanto, temos a igualdade também em(2.6.11). Claramente, a igualdade em (2.6.11) vale também nocaso em que G, além de m arestas isoladas, possui uma quanti-dade arbitrária de vértices isolados.

A determinação precisa da energia de um grafo dependeda descrição completa de seu espectro, tarefa que, pelo que jávimos pode ser realizada apenas para classes muito particularesde grafos. Vamos utilizar o nosso estudo sobre o espectro dosgrafos circulantes para apresentar uma estimativa para a energiade grafos formados a partir de um grafo Kn do qual se retiraum ciclo hamiltoniano, isto é, um ciclo que passa por todosos vértices. Denotemos tal grafo por Kn − H, onde H é umciclo hamiltoniano de Kn. Se o conjunto de vértices de Kn éV = {0, 1, . . . , n−1}, então cada vértice i de Kn−H é adjacentea todo vértice de V − {i}, exceto i+ 1 e i− 1 reduzidos módulon. Portanto, Kn −H é o grafo circulante Ci(n; 1).


O teorema a seguir, provado por Stevanović e Stankovićem [77], responde (negativamente) a uma conjectura anunciadaem [5] afirmando que, a partir de um certo número de vértices,os grafos da forma Kn −H têm energia maior do que a energiado grafo Kn. Grafos com esta propriedade são chamados hiper-energéticos.

Teorema 2.3. Existe n0 ∈ N∗ tal que E(Ci(n, 1)) > 2(n − 1),para todo n ≥ n0.

Demonstração: Usando o estudo feito acima para os autovaloresde um grafo circulante e a Proposição 2.8, concluímos que osautovalores de Ci(n, 1) = Kn −H são α0 = n − 3 e αj = −1 −2cos 2πj

n para j = 1, . . . , n− 1. Logo,

E(Ci(n, 1)) = n− 3 +n−1∑j=1

∣∣∣∣− 1− 2cos2πj

n

∣∣∣∣.Da teoria de integração obtemos a igualdade∫ 2π

0

| − 1− 2cosx|dx = limn→∞2π

n− 1

n−1∑j=1

∣∣∣∣− 1− 2cos2πj

n

∣∣∣∣.Portanto,

limn→∞E(Ci(n, 1))

n− 1=

= limn→∞

[n− 3

n− 1+

1

2π.

2π

n− 1

n−1∑j=1

∣∣∣∣− 1− 2cos2πj

n

∣∣∣∣] == 1 +

1

2π

∫ 2π

0

| − 1− 2cosx|dx.

Observemos que, para x ∈ [0, 2π],

| − 1− 2cosx| =

{1 + 2cosx se cosx ≥ − 1

2

−1− 2cosx se cosx ≤ − 12 ,


ou seja,

| − 1− 2cosx| =

1 + 2cosx se 0 ≤ x ≤ 2π/3

ou 4π/3 ≤ x ≤ 2π;−1− 2cosx se 2π/3 ≤ x ≤ 4π/3.

Então, ∫ 2π

0

| − 1− 2cosx|dx =

=

∫ 2π3

0

(1+2cosx)dx +

∫ 4π3

2π3

(−1−2cosx)dx+∫ 2π

4π3

(1+2cosx)dx.

Efetuando os cálculos, chegamos a

limn→∞E(Ci(n, 1))

n− 1=

= 1 +1

2π

∫ 2π

0

| − 1− 2cosx|dx =4√3

2π+

4

3≈ 2.43599 > 2.

Logo, existe n0 ∈ N∗ tal que E(Ci(n, 1)) > 2(n − 1) para todon ≥ n0. Cálculos computacionais mostram que n0 = 10 [77].

Dados inteiros n, k1 < k2 < . . . < kl < n/2 como antes,o grafo complementar Ci(n, k1, . . . , kl) de Ci(n, k1, . . . , kl) temconjunto de vértices V = {0, 1, . . . , n − 1} em que cada vérticei está ligado a todo vértice de V − {i} exceto i + kr e i − kr,reduzidos módulo n; ou seja, Ci(n, k1, k2, . . . , kl) é o grafo cir-culante Ci(n, {1, 2, . . . , ⌊n2 ⌋} − {k1, k2, . . . , kl}). Ainda em [77],Stevanović e Stanković generalizaram o resultado anterior, esta-belecendo o seguinte teorema:

Teorema 2.4. Sejam l, k1 < k2 < . . . < kl ∈ N∗. Então existen0 ∈ N∗ tal que, para cada n ≥ n0, o grafo Ci(n, k1, k2, . . . , kl)

é hiperenergético.


Demonstração: Sejam l, k1, . . . , kl como no enunciado. Pelo nossoestudo sobre grafos circulantes e ainda pela Proposição 2.8, temosque, para cada n ∈ N∗, os autovalores de Ci(n, k1, k2, . . . , kl) sãodados por λ0 = n− (n− (n− 2l))− l = n− 1− 2l e

λj = −1−l∑

r=1

2coskr2πj

npara j = 1, . . . , n− 1.

Portanto, para cada n ∈ N∗,

E(Ci(n, k1, . . . , kl)) = (n− 1− 2l) +n−1∑j=1

∣∣∣∣∣−1−l∑

r=1

2coskr2πj

n

∣∣∣∣∣ .(2.6.12)

Seguindo o raciocínio utilizado no resultado anterior, é suficienteprovar que

limn→∞E(Ci(n, k1, . . . , kl))

n− 1> 2. (2.6.13)

Chamando ck1,...,klao primeiro membro de (2.6.13) tem-se

ck1,...,kl= 1 + limn→∞

1

n− 1

n−1∑j=1

∣∣∣∣∣−1−l∑

r=1

2coskr2πj

n

∣∣∣∣∣ .Como visto anteriormente,

limn→∞2π

n− 1

n−1∑j=1

∣∣∣∣∣−1−l∑

r=1

2coskr2πj

n

∣∣∣∣∣ ==

∫ 2π

0

∣∣∣∣∣−1−l∑

r=1

2coskrx

∣∣∣∣∣ dx. (2.6.14)

De (2.6.12) e (2.6.14) chega-se então a

ck1,...,kl= 1 +

1

2π

∫ 2π

0

∣∣∣∣∣−1−l∑

r=1

2coskrx

∣∣∣∣∣ dx.


Mas daí, ck1,...,kl> 2 se e somente se∫ 2π

0

∣∣∣∣∣−1−l∑

r=1

2coskrx

∣∣∣∣∣ dx > 2π.

Para mostrar isso, seja f : [0, 2π] → R dada por f(x) = −1 −∑lr=1 2 cos krx e consideremos as funções f+ e f− de [0, 2π] em

R definidas por

f+(x) =

{f(x), se f(x) ≥ 0;

0, se f(x) < 0

e

f−(x) =

{0, se f(x) ≥ 0;

−f(x), se f(x) < 0.

Valem as relações |f | = f++ f− e f = f+− f−, sendo que f+ ef− são funções contínuas, pois f é contínua. Podemos escreverentão:∫ 2π

0

|f(x)|dx =

∫ 2π

0

[2f+(x)− f+(x) + f−(x)]dx =

=

∫ 2π

0

[2f+(x)]dx +

∫ 2π

0

[−f(x)]dx =

∫ 2π

0

[2f+(x)]dx+ 2π.

Devemos mostrar que

max[0,2π]

f(x) = max[0,2π]

f+(x) > 0,

pois daí segue que∫ 2π

0[f+(x)]dx > 0 e, portanto,

∫ 2π

0|f(x)|dx >

2π. Considere para n > 4kl, o grafo G = Ci(n, k1, . . . , kl).Seus autovalores são n − 1 − 2l e −1 −

∑li=1 2coskr

2πjn para

j = 1, 2, . . . , n − 1. O segundo maior autovalor de G é igual a−1 −

∑li=1 2coskr

2πj0n para algum j0 ∈ {1, 2, . . . , n− 1}. Como

visto anteriormente, no grafo Ci(n, k1, k2, . . . , kl) o vértice u é

adjacente a todos os vértices de V − {u} exceto u± kr(mod n),r = 1, 2, . . . , l. Então, para cada u ∈ {0, 1, . . . , n − 1}, entre osvértices u, u + kl, u + 2kl e u + 3kl de G reduzidos módulo n,temos que {u, u+2kl}, {u, u+3kl} e {u+ kl, u+3kl} são paresde vértices adjacentes, enquanto {u, u + kl}, {u + kl, u + 2kl}e {u + 2kl, u + 3kl} são pares de vértices não-adjacentes. Por-tanto, o subgrafo de G induzido pelos vértices u, u+kl, u+2kl eu+ 3kl é isomorfo a P4, cujo segundo maior autovalor é igual a−1+

√5

2 ≈ 0.618. Pelo Teorema de Entrelaçamento para matriz deadjacência (Teorema 2.1), o segundo maior autovalor de G é, nomínimo, igual ao segundo maior autovalor de qualquer subgrafoinduzido de G. Portanto,

−1−l∑

i=1

2coskr2πj0n≥ −1 +

√5

2> 0,

como queríamos.

2.7 Exercícios

1. Seja G um grafo com n vértices, m arestas e autovaloresλ1, · · · , λn. Mostre que

∑n1≤i<j≤n λiλj = −m.

2. Desenhe uma representação do grafo cuja matriz de adja-cência é

A =

0 1 0 0 1 1

1 0 1 0 0 1

0 1 0 1 0 1

0 0 1 0 1 1

1 0 0 1 0 1

1 1 1 1 1 0

.


Para este grafo, determine o polinômio característico, ograu máximo, o grau mínimo e o diâmetro. O cálculo dosautovalores desse grafo não é trivial. Como é possível afir-mar que seu índice está compreendido entre 3, 33 e 5?

3. Os grafos cúbicos da Figura 23 ilustram a capa de um clás-sico livro de Teoria dos Grafos [50]. Prove que eles são doisa dois não isomorfos. Verifique se entre eles se há algumpar coespectral.

Figura 23 – Grafos cúbicos de ordem 10

4. Dentre os grafos da Figura 23, chame de H aquele que temum único par de ciclos disjuntos de comprimento 4. Calculequantos ciclos de comprimento 5 tem H.

5. O grafo do canto inferior direito da Figura 23 é conhecidona literatura como o grafo de Petersen e é denotado por P(veja o Exemplo 1.3). O grafo P é muito utilizado comocontraexemplo de grafos que não satisfazem certas pro-priedades. Para este grafo determine:

(i) sua matriz de adjacência;

2.7 Exercícios 67

(ii) seu índice, sem fazer nenhum cálculo:

(iii) os coeficientes a2 e a3 do seu polinômio caracterís-tico, também sem calcular o determinante.

6. O grafo de Petersen tem um autovalor igual a 3 com multi-plicidade algébrica igual a 1. Esta afirmação é verdadeira?Prove que a soma de seus autovalores ao quadrado é iguala 30. Responda estas questões sem fazer nenhum cálculoexaustivo.

7. Grafos com a mesma sequência de graus sempre têm poli-nômios característicos iguais? Justifique sua resposta.

8. Um grafo como o da Figura 24, constituído por um ca-minho Pt e uma clique Kn−t com um único vértice emKn−t ∩ Pt é conhecido como pipa . Mostre que o númeromínimo de autovalores distintos do grafo pipa é t+ 1.

Figura 24 – Um grafo pipa.

9. É possível encontrar grafos não isomorfos para uma mesmasequência de graus? Em caso negativo, justifique sua res-posta. Em caso positivo, apresente um par de grafos coma mesma sequência de graus.


10. Mostre que grafos isomorformos têm matrizes de adjacên-cia semelhantes.

11. Mostre que a matriz de adjacência do grafo complementarde um grafo G de ordem n é A(G) = J − In −A(G), ondeJ é a matriz cujas entradas são todas iguais a 1.

12. Determine a matriz de adjacência de P , sabendo-se queP é o grafo de Petersen (Exercício 5). Determine tambémos coeficientes a2 e a3 de seu polinômio característico, uti-lizando somente informações estruturais de P .

13. O cubo é o grafo da Figura 25. Prove que o cubo é bipar-tido. Determine o espectro do cubo sem calcular o deter-minante.

Figura 25 – Cubo

14. Encontre um grafo que tenha índice estritamente maiorque seu grau mínimo e estritamente menor que seu graumáximo.

15. Mostre que se H é um subgrafo de um grafo G entãoind(H) ≤ ind(G). Em geral, esta propriedade só é vál-ida para o índice de G. Sendo assim, encontre um grafo G

em que λ2(H) > λ2(G). No entanto, se H é um subgrafoinduzido de G tem-se que λ2(H) ≤ λ2(G). Prove este fato.

16. Mostre que a propriedade acima se verifica no grafo cubo.


Este e os demais capítulos desta monografia abordamas principais matrizes que representam grafos. Em particular,este capítulo é voltado exclusivamente para a matriz de adja-cência, mas nenhuma das referências seguintes são voltadas ex-clusivamente para ela. Sendo assim, serão indicações recorrentesnos próximos capítulos. O primeiro livro em Teoria Espectral deGrafos deve-se a D.Cvetković, M.Doob e H. Sachs [23], já está naterceira edição, [24], e tem como enfoque principal propriedadesestruturais de grafos relacionados com a matriz de adjacência.No entanto, para o estudante que deseja se iniciar na área, estanão deve ser a primeira escolha. Para estes, recomendamos asseguintes e clássicas referências: Biggs [10], Godsil & Royle [41]e Beineke & Wilson, [8]. Recentemente, D. Cvetković, P. Rowlin-son e S. Simić lançaram o livro introdutório [31], que veio supriruma lacuna há muito tempo existente. Em língua portuguesa,embora ainda não haja disponível um livro introdutório de Teo-ria Espectral de Grafos publicado em larga escala, podemos re-comendar o excelente texto de Donadelli [35].

3 Matriz de incidência

Neste capítulo trataremos da matriz de incidência. Osresultados espectrais sobre esta matriz estão relacionados como grafo linha. Para nosso propósito, a sua importância está nofato que ela fornece relações importantes que serão utilizadas nospróximos capítulos, principalmente para obter resultados estru-turais de grafos a partir da matriz Laplaciana.

3.1 Introdução

A matriz de incidência de um grafo fornece uma de-scrição das relações de incidência das arestas nos vértices dografo. Tem grande importância teórica como veremos no próximocapítulo, onde algumas de suas propriedades serão utilizadas nademonstração de resultados sobre a matriz Laplaciana, ainda queisto não apareça explicitamente no enunciado. O mesmo podeser observado com relação à utilização da matriz de incidênciana obtenção de propriedades do grafo-linha de um grafo, comoveremos ainda neste capítulo.

3.2 Matriz de incidência e grafo-linha de um grafo

Definição 3.1. A matriz de incidência de um grafo G comn vértices e m arestas, denotada por B(G), é a matriz de ordem


n×m cujas entradas são:

bij =

{1, se ej é uma aresta incidente no vértice vi;0, caso contrário.

Figura 26 – Grafo do Exemplo 3.1.

Exemplo 3.1. Para o grafo da Figura 26, a matriz de incidênciaé

B(G) =

1 1 0 0 0 0

0 1 1 0 1 1

1 0 1 1 0 0

0 0 0 0 0 1

0 0 0 1 1 0

.

Lema 3.1. Sejam G um grafo com m arestas, B = B(G) suamatriz de incidência, ℓ(G) o seu grafo-linha e Aℓ a matriz deadjacência de ℓ(G). Então BTB = 2Im +Aℓ.

Demonstração: Considere αij = (BTB)ij . Tem-se que αij é oproduto interno da i-ésima linha de BT com a j-ésima colunade B . Logo αij = 1 se as arestas ei e ej de G têm um vérticeem comum e αij = 0, em caso contrário; além disso, αij = 2, sei = j.

3.2 Matriz de incidência e grafo-linha de um grafo 73

Tomemos agora βij = (Aℓ)ij . Então βij = 1, se asarestas ei e ej de G incidem em um mesmo vértice: neste caso,se i ̸= j , (2Im +Aℓ)ij = 1, senão (2Im +Aℓ)ij = 2 . Finalmente,se ei e ej não têm vértice comum em G então βij = 0 . Isto provao lema.

Proposição 3.1. Se λ é um autovalor do grafo-linha ℓ(G) deum grafo G então λ ≥ −2.

Demonstração: Como BTB = 2I+Aℓ e BTB é uma matriz semi-definida positiva, se λ é autovalor do grafo-linha então existevetor v não nulo tal que

(BTB)v = (2I +Aℓ)v = 2v + λv = (2 + λ)v.

Logo, 2 + λ é autovalor de BTB e, portanto, 2 + λ ≥ 0. Istoimplica em λ ≥ −2.

Apesar de restritiva, a condição da proposição anteriornão é suficiente para caracterizar grafos-linha, isto é, existemgrafos cujos autovalores são todos maiores ou iguais a −2 e nãosão grafos-linha de nenhum grafo. A caracterização dos grafosque têm menor autovalor igual a −2 foi obtida em 1976 [17].

Lema 3.2. Sejam B = B(G) a matriz de incidência de um grafoG com n vértices e D a matriz diagonal n × n cujas entradascorrespondem aos graus dos vértices de G . Então BBT = D+A,onde A é a matriz de adjacência de G .

Demonstração: Se i = j, o produto da i-ésima linha de B pelaj-ésima coluna de BT é o grau do vértice vi em G . Se i ̸= j ,


a entrada ij em BBT é 1 ou 0 , conforme vi e vj sejam ou nãoadjacentes em G .

Lema 3.3. Sejam B = B(G) a matriz de incidência de um grafoG, ℓ(G) o seu grafo-linha e Aℓ a matriz de adjacência de ℓ(G).Se existe vetor v ̸= 0 tal que Bv = 0 então −2 é um autovalorde Aℓ .

Demonstração: Já vimos que BTB = 2I +Aℓ . Seja v ̸= 0 vetortal que Bv = 0 . Daí (BTB)v = BT (Bv) = BT0 = 0 . Logo(2I +Aℓ)v = 2Iv+Aℓv = 2v+Aℓv = 0 , ou seja, Aℓv = −2v .Como v ̸= 0 temos que −2 é autovalor para Aℓ .

Lema 3.4. Sejam B = B(G) a matriz de incidência de um grafoG que contém um ciclo de comprimento par. Então existe umvetor v ̸= 0 tal que Bv = 0 .

Demonstração: Seja u1, u2, ..., u2k um ciclo de comprimento 2k

em G . Tome o vetor v = [v1 v2 · · · vn]T tal que vi = (−1)i parai , 1 ≤ i ≤ 2k e vi = 0 para i > 2k . Verifica-se que Bv = 0 .

Exemplo 3.2. Para o grafo da Figura 27, o vetor

v = [(−1)1, (−1)2, (−1)3, (−1)4, 0]T

3.2 Matriz de incidência e grafo-linha de um grafo 75


satisfaz

Bv =

1 0 0 1 0

1 1 0 0 0

0 1 1 0 0

0 0 1 1 0

0 0 0 0 1

0 0 0 0 1

−11

−11

0

=

0

0

0

0

0

0

.

Decorre imediatamente dos dois últimos Lemas que seG contém um ciclo de comprimento par então −2 é autovalor deℓ(G). A recíproca é também verdadeira [22]. Prova-se de modosemelhante que G tem dois ciclos ímpares na mesma componenteconexa se e somente se −2 é autovalor de G [23].

Proposição 3.2. Se G é um grafo k-regular com n vértices em arestas então Pℓ(G)(λ) = (λ+ 2)m−nPG(λ− k + 2) .


Demonstração: Considere as matrizes

U =

[λIn −B0 Im

]e V =

[In B

BT λIm

],

onde B é a matriz de incidência do grafo G. Então

UV =

[λIn −BBT 0

BT λIm

]e V U =

[λIn 0

λBT λIm −BTB

].

Como det(UV ) = det(V U) então λm det(λIn−BBT ) = λn det(λIm−BTB) . Logo,

pℓ(G)(λ) = det(λIm −Aℓ) = det((λ+ 2)Im −BTB) =

= (λ+ 2)m−n det((λ+ 2)In −BBT ) =

= (λ+ 2)m−n det((λ+ 2− k)In −A) =

= (λ+ 2)m−npG(λ− k + 2) .

Corolário 3.1. Se G é um grafo regular de grau k com

spect(G) =

[k λ1 · · · λs−1

1 m1 · · · ms−1

]

então

spect(ℓ(G)) =

[2k − 2 k − 2 + λ1 · · · k − 2 + λs−1 −2

1 m1 · · · ms−1 m− n

].

Demonstração: Segue imediatamente da Proposição anterior.

Exemplo 3.3. Seja G = K5. Como

spect(K5) =

[4 −11 4

],

o Corolário 3.1 garante que

spect(ℓ(K5)) =

[6 1 −21 4 5

].

Como ℓ(K5) é um grafo regular, pois K5 é regular, segue daProposição 2.8, que

spect(ℓ(K5)) =

[3 1 −21 4 5

].

No Exemplo 1.3, vimos que ℓ(K5), complementar do grafo-linhade K5, é conhecido como grafo de Petersen.

3.3 Exercícios

1. Desenhe um grafo desconexo com 9 vértices, grau máximo3 e 2 componentes conexas. Para este grafo, determine asmatrizes de adjacência e de incidência.

2. Considere a matriz de incidência de um grafo G dadaabaixo:

B =

1 0 0 1 1 0

1 1 0 0 0 1

0 1 1 0 1 0

0 0 1 1 0 1

a) Dê o grau máximo e o grau mínimo do grafo.

b) Desenhe o grafo G.

3. Mostre que se duas árvores têm grafos-linha isomorfos en-tão elas são isomorfas.

4. Diga se cada afirmação abaixo é verdadeira ou falsa, justi-ficando sua resposta.

a) A soma das entradas de cada linha da matriz de in-cidência de um grafo k−regular é igual a k;

b) A soma das entradas de cada coluna da matriz deincidência de um grafo é constante;

c) Se a matriz de incidência de um grafo é n×m então amatriz de incidência de seu complementar é tambémn×m;

d) O número de triângulos do grafo ℓ(K4) é zero;

e) O número de vértices isolados de um grafo corre-sponde ao número de linhas nulas na matriz de in-cidência.

5. Mostre que G é um grafo bipartido se e somente se D(G)+

A(G) e D(G)−A(G) são semelhantes.

6. Seja G um grafo-linha tal que u e v são vértices de G com omesmo conjunto de vértices adjacentes. Mostre que u = v.

7. Prove que um grafo conexo é isomorfo ao seu grafo-linhase e somente se ele é um ciclo.

8. Se G é o grafo da Figura 26 encontre v ̸= 0 tal que Bv = 0.Podemos dizer que −2 é autovalor de l(G)? Justifique.



Matriz de incidência de um grafo e o conceito de grafo-linha são dois tópicos abordados em Teoria Algébrica e Espectraldos Grafos. Por isso, as indicações feitas aqui não poderiam seroutras que não aquelas já citadas nas Notas Bibliográficas doCapítulo 2. No entanto, gostaríamos de acrescentar uma refer-ência interessante dedicada aos grafos-linha e suas generaliza-ções. Trata-se do livro recente de Cvetković, Rowlinson e Simić[29] em que são tratados os autovalores da matriz de adjacênciade grafos-linha. Além desse, podemos destacar entre os livrosjá citados, aqueles em que o leitor poderá encontrar os tópicosdeste capítulo abordados com mais profundidade. Em Harary[50] há um capítulo inteiro dedicado aos grafos-linha e em God-sil e Royle [41] há, pelo menos, duas subseções sobre matrizes deincidência.

81

4 Matriz Laplaciana

A matriz Laplaciana de um grafo e, em especial, seumaior e segundo menor autovalores, desempenham papel re-levante em diversas aplicações. Neste capítulo, além das pro-priedades básicas desta matriz, apresentamos o Teorema da Matriz-árvore, que, em sua versão espectral (Corolário 4.2), determinao número de árvores geradoras de um grafo em função dos auto-valores da matriz Laplaciana. Vemos ainda aplicações do estudodesses autovalores em otimização combinatória, em Química eem Biologia.

4.1 Conceitos e resultados preliminares

Definição 4.1. Seja D a matriz diagonal dos graus dosvértices de um grafo G (ou seja, a matriz D tal que Dii = d(vi))

e seja A a matriz de adjacência de G . A matriz

L = D −A

é chamada matriz Laplaciana ou Laplaciano do grafo G.Quando necessário, usaremos L(G) em lugar de L.

Exemplo 4.1. Para o grafo da Figura 28, temos

D =

3 0 0 0 0

0 2 0 0 0

0 0 1 0 0

0 0 0 3 0

0 0 0 0 1

e A =

0 1 1 1 0

1 0 0 1 0

1 0 0 0 0

1 1 0 0 1

0 0 0 1 0

.

82 Matriz Laplaciana

Logo,

L =

3 −1 −1 −1 0

−1 2 0 −1 0

−1 0 1 0 0

−1 −1 0 3 −10 0 0 −1 1

.


Definição 4.2. O espectro do Laplaciano L de um grafo G,denotado por ζ(G), é a matriz-linha cujos elementos são todosos autovalores de L ordenados de forma não crescente. Assim,se µ1 ≥ . . . ≥ µn são os autovalores de L então

ζ(G) = (µ1 , . . . , µn).

Exemplo 4.2. Para os grafos G1 e G2 da Figura 29, temosζ(G1) = (4, 3, 1, 0) e ζ(G2) = (4, 3, 2, 1, 0, 0, 0). Notar que onúmero de componentes conexas de cada grafo coincide exata-mente com a multiplicidade do 0, que é autovalor Laplaciano deambos. Estes fatos valem para todos os grafos, como mostramosna sequência.

A próxima definição considera excepcionalmente que aografo G é atribuída uma orientação.

4.1 Conceitos e resultados preliminares 83

Figura 29 – Grafos G1 e G2.

Definição 4.3. Seja G um grafo. A matriz β de incidênciacom respeito a uma orientação dada é aquela cujas entradassão

βij =

+1, se vi é o vértice onde chega ej ;

−1, se vi é o vértice de onde parte ej ;

0, nos outros casos.

Não é difícil provar que L = ββT . Segue daí que o LaplacianoL é uma matriz semidefinida positiva que tem, portanto, todosos seus autovalores maiores ou iguais a zero .

Lema 4.1. Seja G um grafo com n vértices e seja β a matrizde incidência de G com respeito a uma orientação dada. Entãoo posto r(β) de β é n − ω, onde ω é o número de componentesconexas de G .

Demonstração: Sejam G1, . . . , Gω as componentes conexas dografo G, cada Gi com ni vértices. Então β tem uma decom-posição em blocos de modo que, para cada i, 1 ≤ i ≤ ω, β(i)

é a matriz de incidência (com respeito à orientação fixada) da


i-ésima componente conexa de G. Assim,

β =

β(1) 0 0 · · · 0

0 β(2) 0 · · · 0

0...

......

......

... 0 β(ω−1) 0

0 · · · 0 0 β(ω)

.

Para cada i, 1 ≤ i ≤ ω, como a soma dos elementos de cadacoluna de β(i) é nula, o posto desta matriz é, no máximo, ni−1,e portanto, r(β) ≤ n − ω. Para concluirmos que r(β) = n − ω,basta então mostrar que r(β(i)) = ni− 1 para cada i, 1 ≤ i ≤ ω.Para este fim, fixado i, mostremos que o posto de (β(i))T , quecoincide com o posto de β(i), é exatamente ni − 1, mostrandoque o núcleo N((β(i))T ) de (β(i))T tem dimensão 1. Basta entãoexibir uma base para este subespaço, a saber, 1 = [1 1 . . . 1]T .Ora, claramente, 1Tβ(i) = 0, ou seja, 1 ∈ N((β(i))T ). Só faltamostrar que 1 gera N((β(i))T ) .

Seja então x ∈ N((β(i))T ). Consideremos duas coorde-nadas xl e xk quaisquer de x, relacionadas respectivamente aosvértices vl e vk de Gi. Como Gi é conexo, existe um subconjunto{vj1, vj2, . . . , vjr} onde l = j1 e k = jr, tais que existe umaaresta entre vjp e vj(p+1), para cada p = 1, 2, . . . , r − 1. Cor-respondendo a cada uma das r − 1 arestas {vjp, vj(p+1)}, existeuma coluna cp em β(i) (não necessariamente a p-ésima) cujas en-tradas de ordem jp e j(p+ 1) valem uma 1 e outra -1, sendo asoutras iguais a zero. Como xTβ(i) = 0, segue-se que xT cp = 0,e daí, xjp = xj(p+1). Mas isto vale para todo p = 1, 2, . . . , r − 1.Logo, xl = xk, para cada l e k. Logo x = α1, para algum escalarα e assim, 1 gera N((β(i))T ).

4.1 Conceitos e resultados preliminares 85

Proposição 4.1. O posto r(L) da matriz Laplaciana L de umgrafo G com n vértices é n − ω, onde ω é o número de compo-nentes conexas de G .

Demonstração: A afirmação decorre diretamente do lema ante-rior. De fato, o posto de L é igual ao posto da matriz de incidên-cia β com respeito a (qualquer) orientação considerada sobre G,pois L = ββT .

Segue da proposição anterior que 0 é o menor autovalorda matriz Laplaciana de qualquer grafo. Este fato, no entanto,pode ser provado diretamente, como é feito no item (i) da próx-ima proposição.

Proposição 4.2. Sejam µ1 ≥ µ2 ≥ . . . ≥ µn os autovalores damatriz Laplaciana L de um grafo G. Então

(i) µn = 0 com autovetor associado 1 = [1, 1, . . . , 1]T ;

(ii) G é conexo se, e somente se, µn−1 > 0;

(iii) se G é regular de grau k então cada µi = k − λn−i, ondeλi é autovalor da matriz de adjacência A de G.

Demonstração: (i) Basta notar que a soma dos elementos de umalinha qualquer de L é zero, logo L.1 = 0 = 0.1.(ii) Pela Proposição anterior, G é conexo se, e somente se o postode L é n− 1, o que prova a afirmação.(iii) Segue direto da definição de L, observando que, se G é reg-

ular de grau k então

D =

k 0 0 ... 0

0 k 0 ... 0

... ... ... ... ...

0 0 0 ... k

.

Para a matriz Laplaciana vale um resultado de entre-laçamento, conhecido como Teorema de entrelaçamento para ma-triz Laplaciana, análogo ao Teorema 2.1. A prova é tambémdecorrência do Teorema 7.1.

Teorema 4.1. Seja G = G(V,E) um grafo com n vértices e sejae ∈ E. Se G′ = G+ {e} então µj(G) ≤ µj(G

′) ≤ µj+1(G), paratodo j ∈ {1, 2, . . . , n− 1}.

Notamos que, comon∑

i=1

(µi(G′)− µi(G)) = 2m+ 2− 2m = 2,

pelo menos uma das desigualdades acima deve ser estrita.

4.2 O Teorema da Matriz-árvore

A determinação do número de árvores geradoras de umgrafo é um dos problemas mais antigos e famosos da Teoria deGrafos e foi resolvido por Gustav Kirchhoff, que em 1847, estu-dando circuitos elétricos, provou o resultado que ficou conhecidocomo Teorema da Matriz-árvore. Além da importância em con-textos diversos como a representação de moléculas em Químicae o desenho de redes, do ponto de vista da Matemática, o estudodeste problema se constitui numa bela aplicação de conceitos

4.2 O Teorema da Matriz-árvore 87

básicos de Álgebra Linear, teoria de determinantes e de grafos.O desenvolvimento que apresentamos a seguir pode ser encon-trado em [10].

Figura 30 – K4 e suas 16 árvores geradoras.

Definição 4.4. Uma árvore geradora de um grafo G é umsubgrafo que tem os mesmos vértices de G e é uma árvore.

Claramente, grafos desconexos não possuem árvores ge-radoras. Por outro lado, todo grafo conexo tem pelo menos uma


árvore geradora (se o grafo não é uma árvore, podemos removeruma aresta de cada vez, de cada ciclo, até não haver mais ciclos;o subgrafo obtido será uma árvore geradora do grafo inicial).Um grafo pode ter um número elevado de árvores geradoras,dependendo de quantos vértices e ciclos possua. Na Figura 30,vemos o grafo K4 e suas 16 árvores geradoras.

O Teorema da Matriz-árvore na sua versão original,afirma que o número de árvores geradoras de um grafo é dado porqualquer cofator de sua matriz Laplaciana. Apesar da abrangên-cia do resultado, veremos posteriormente que, dependendo dotipo de grafo, sua aplicação pode requerer cálculos bastante elab-orados.

Em toda esta seção, G é um grafo conexo com n vérticesv1, v2, ..., vn e m arestas e1, e2, ..., em, cuja matriz Laplaciana éL. Por β, denotamos a matriz de incidência de G com respeitoa uma orientação (como se poderá constatar, os resultados nãodependerão da orientação escolhida). Indicamos por J a matrizquadrada de ordem n cujas entradas são todas iguais a 1.

Lema 4.2. A matriz adjunta de L, denotada adj(L), é um múlti-plo de J .

Demonstração: Pela Proposição 4.1, a matriz L tem posto iguala n−1, pois G é conexo. Além disso, o núcleo de L tem dimensão1 e é gerado por 1 = [1 . . . 1]T . Por outro lado, como

L.adj(L) = det(L).I = 0.I = O

(onde O é a matriz nula de ordem n), então cada coluna deadj(L) pertence ao núcleo de L, sendo assim um múltiplo do ve-tor 1T . Mas L é matriz simétrica; logo adj(L) é simétrica e tem,


portanto, todas as entradas iguais. O resultado está provado.

Lema 4.3. Qualquer submatriz quadrada de β tem determinante0, 1 ou −1.

Demonstração: Seja S uma submatriz quadrada de β. Se cadacoluna de S tem duas entradas não nulas então estas entradassão 1 e −1 e, portanto, cada coluna tem soma igual a zero. LogoS é singular e det(S) = 0. Suponhamos agora que pelo menosuma coluna de S tenha exatamente uma entrada não nula. Nestecaso, expandimos o determinante de S em termos desta colunae obtemos det(S) = ±det(S′), onde S′ é matriz com uma linha euma coluna menos do que S. Continuando este processo, cheg-amos a determinante nulo ou a uma entrada não nula de β e,portanto, o resultado está provado.

Lema 4.4. Considere qualquer submatriz de β obtida tomando-se n − 1 de suas colunas. Esta matriz de ordem n × (n − 1)

corresponde a um subgrafo H de G contendo todos os seus vér-tices. Então, removida qualquer linha da submatriz, a matriz re-sultante β′ é quadrada de ordem n− 1 e tem |det(β′)| = 1 ou 0,conforme o subgrafo H seja ou não uma árvore (se for árvore,H será uma árvore geradora de G).

Demonstração: Sem perda de generalidade, removamos a n-ésimalinha da submatriz. Pelo Lema 4.3, |det(β′)| = 1 ou 0. Suponha-mos inicialmente que o subgrafo H não seja uma árvore. Comn vértices e n − 1 arestas, H é necessariamente desconexo e,portanto, tem uma componente que não contém o vértice vn.


Como as colunas de β′ correspondentes às arestas desta compo-nente somam zero (pois cada aresta liga dois vértices da mesmacomponente), as linhas de β′ são linearmente dependentes e, por-tanto, det(β′) = 0.

Suponhamos agora que H seja uma árvore. Então pode-mos renomear suas arestas e vértices (diferentes de vn) da seguintemaneira: chamemos u1 ̸= vn a um vértice de grau 1 de H

(qualquer árvore tem pelo menos dois vértices de grau 1, [50]).Chamemos de y1 a aresta que incide em u1. Seja u2 ̸= vn umvértice extremo de H − {u1} e seja y2 a aresta incidente emu2. Continuando este processo, notamos que cada aresta yi in-cide no vértice vi e em algum vértice vj com j > i. Mas estarenomeação dos vértices de H determina uma nova matriz β′′

que pode ser obtida de β′ por permutação de suas linhas. Daí|det(β′)| = |det(β′′)|. Além disso, β′′ é uma matriz triangularinferior cujas entradas na diagonal principal são ±1. Portanto,| det(β′) |=| det(β′′) |= 1.

O Teorema da Matriz-árvore afirma que o número deárvores geradoras de G é igual a qualquer cofator de L. Maisprecisamente:

Teorema 4.2 (Teorema da Matriz-árvore).

adj(L) = τ(G).J ,

onde τ(G) indica o número de árvores geradoras de G

Demonstração: Pelo Lema 4.2, basta mostrar que qualquer cofa-tor de G é τ(G). Seja β0 a matriz obtida de β pela retirada desua última linha. Retirando-se também a última linha e a última


coluna de L, observamos que a submatriz obtida é exatamenteβ0β

T0 . Assim, det(D0D

T0 ) é o cofator do elemento lnn de L. Ex-

pandindo este determinante pela fórmula de Binet-Cauchy [52],obtemos

det(β0βT0 ) =

∑U

det(βU )det(βtU ),

onde o somatório é considerado sobre todos os subconjuntos U

de {1, . . . , n} com n− 1 elementos. Assim, βU denota a subma-triz quadrada de β0 cujas colunas correspondem exatamente aoselementos em U . Pelos Lemas 4.3 e 4.4, det(βU ) ̸= 0 se e somentese o subgrafo cujas arestas estão em U e tem todos os vértices deG é uma árvore geradora de G, quando então det(βU ) = 1 ou−1.Como det(βU ) = det(βt

U ) temos que det(β0βt0) = τ(G). Daí,

adj(L) = τ(G)J.

Exemplo 4.3. Vamos calcular o número de árvores geradorasdo ciclo Cn. O Laplaciano de Cn é

L(Cn) =

2 −1 0 . . . 0 0 −1−1 2 −1 . . . 0 0 0

0 −1 2 . . . 0 0 0...

......

. . ....

......

0 0 0 . . . 2 −1 0

0 0 0 . . . −1 2 −1−1 0 0 . . . 0 −1 2

n

.

Para determinarmos τ(Cn), calculemos o cofator de ordem 1×1


do seu Laplaciano. Temos que

∆11 = (−1)2det

2 −1 0 . . . 0 0 0

−1 2 −1 . . . 0 0 0

0 −1 2 . . . 0 0 0...

......

. . ....

......

0 0 0 . . . 2 −1 0

0 0 0 . . . −1 2 −10 0 0 . . . 0 −1 2

(n−1)

.

Somemos agora as linhas 2, 3, . . ., n−1 à primeira linha, obtendoa seguinte matriz, cujo determinante é igual ao da anterior:

1 0 0 . . . 0 0 1

−1 2 −1 . . . 0 0 0

0 −1 2 . . . 0 0 0...

......

. . ....

......

0 0 0 . . . 2 −1 0

0 0 0 . . . −1 2 −10 0 0 . . . 0 −1 2

(n−1)

.

Somamos então a primeira linha à segunda e obtemos

1 0 0 . . . 0 0 1

0 2 −1 . . . 0 0 1

0 −1 2 . . . 0 0 0...

......

. . ....

......

0 0 0 . . . 2 −1 0

0 0 0 . . . −1 2 −10 0 0 . . . 0 −1 2

(n−1)

.


Repetindo este processo n− 2 vezes chegamos à matriz

1 0 0 . . . 0 0 1

0 1 0 . . . 0 0 2

0 0 1 . . . 0 0 3...

......

. . ....

......

0 0 0 . . . 1 0 n− 3

0 0 0 . . . 0 1 n− 4

0 0 0 . . . 0 0 n

(n−1)

,

que é uma matriz triangular superior com determinante igual aode ∆11 e valendo n. Logo, τ(Cn) = n.

Exemplo 4.4. Vamos calcular o número de árvores geradorasdo grafo completo Kn. É fácil verificar que o Laplaciano de Kn

é L(Kn) = nI − J , ou seja,

L =

n− 1 −1 −1 . . . −1−1 n− 1 −1 . . . −1−1 −1 n− 1 . . . −1...

......

. . ....

−1 −1 −1 . . . n− 1

n

. (4.2.1)

Calculando o cofator de ordem 1× 1 de L obtemos:

∆11 = (−1)2det

n− 1 −1 . . . −1−1 n− 1 . . . −1−1 −1 . . . −1...

.... . .

...−1 −1 . . . n− 1

(n−1)


= det

1 1 1 . . . 1

−1 n− 1 −1 . . . −1−1 −1 n− 1 . . . −1...

......

. . ....

−1 −1 −1 . . . n− 1

(n−1)

(4.2.2)

= det

1 1 1 . . . 1

0 n 0 . . . 0

0 0 n . . . 0...

......

. . ....

0 0 0 . . . n

(n−1)

= nn−2 (4.2.3)

A matriz em 4.2.2 foi obtida da anterior somando-se as lin-has 2, 3, . . . , n − 1 à primeira linha. Já a matriz em 4.2.3 foiobtida de 4.2.2 somando-se a primeira linha a todas as outras,chegando assim a uma matriz triangular superior, cujo determi-nante é exatamente nn−2. Portanto, τ(Kn) = nn−2 (isto implicaem adj(nI − J) = nn−2J).

Os dois próximos resultados são corolários do Teoremada Matriz-árvore que serão utilizados na determinação do númerode árvores geradoras de alguns tipos de grafos.

Corolário 4.1. O número de árvores geradoras de G é dado por

τ(G) = n−2det(J + L).

Demonstração: É fácil ver que nJ = J2 e que JL = LJ = O.A seguinte sequência de igualdades, que usa a fórmula final do


Exemplo 4.4, prova então o resultado:

(nI − J)(J + L) = nJ + nL− J2 − JL = nL ;

adj[(nI − J)(J + L)] = adj(nL) ;

adj(J + L)adj(nI − J) = adj(nL) ;

adj(J + L)nn−2J = nn−1adj(L) ;

adj(J + L)J = nτ(G)J ;

(J + L)adj(J + L)J = (J + L)nτ(G)J ;

det(J + L)J = nτ(G)J2 ;

det(J + L)J = n2τ(G)J ;

τ(G) = n−2det(J + L) .

O primeiro item do resultado a seguir fornece τ(G) emfunção dos autovalores não nulos da matriz Laplaciana de G.

Corolário 4.2. Se µ1, . . . , µn−1 são os autovalores não nulosde L então

τ(G) =µ1µ2 . . . µn−1

n.

Além disso, se G é um grafo k-regular então

τ(G) = n−1s−1∏r=1

(k − λr)mr = n−1p′G(k),

onde p′G denota a derivada do polinômio característico pG damatriz de adjacência A de G e, para cada i, 1 ≤ i ≤ s− 1, λi éum autovalor de A com multiplicidade mi.


Demonstração: Como L e J comutam, é possível mostrar que osautovalores de J + L são a soma dos correspondentes autovalo-res de L e J . Os autovalores de J são n, com multiplicidade 1,e 0 com multiplicidade n− 1. Logo, os autovalores de J +L sãon, µ1, . . . , µn−1. Como o determinante é o produto dos autovalo-res, pelo Corolário 4.1 temos o resultado.

Agora, se G é um grafo k-regular, segue da Proposição4.2 que cada autovalor λ de A é igual a k − µ, onde µ é umautovalor do Laplaciano. A primeira igualdade segue agrupando-se os autovalores de A de acordo com as suas multiplicidades.Além disso, derivando o polinômio característico de A que é dadopor

pG(x) = (x− k)(x− λ1)m1 . . . (x− λr)

mr ,

obtemos

p′G(x) = (x− λ1)m1 . . . (x− λr)

mr +Φ,

onde Φ é a soma de produtos contendo o termo (x − k). Logo,p′G(k) = (k − λ1)

m1 . . . (k − λr)mr . Daí,

τ(G) = n−1s−1∏r=1

(k − λr)mr = n−1p′G(k).

Exemplo 4.5. Suponhamos que G seja k-regular. Determinare-mos o número de árvores geradoras do grafo-linha de G. DoCorolário 4.2, temos que

τ(G) = n−1p′G(k) e τ(ℓ(G)) = m−1p′ℓ(G)(2k − 2),

pois ℓ(G) é (2k−2)-regular. A partir da Proposição 3.2, obtemosentão

p′ℓ(G)(λ) = (m−n)(λ+2)m−n−1pG(λ+2−k)+(λ+2)m−np′G(λ+2−k).


Quando λ = 2k − 2 obtemos

p′ℓ(G)(2k − 2) = (m− n)(2k)m−n−1pG(k) + (2k)m−np′G(k).

Então, p′ℓ(G)(2k − 2) = (2k)m−np′G(k). Daí

τ(ℓ(G)) = m−1p′ℓ(G)(2k − 2) =

= m−1(2k)m−np′G(k) = m−1n(2k)m−nτ(G).

Como 2m = nk, chegamos a

τ(ℓ(G)) = m−12mk−12m−nkm−nτ(G) = 2m−n+1km−n−1τ(G).

Para G = K4, por exemplo, τ(ℓ(G)) = 23.3.16 = 384.

Nos dois próximos exemplos, determinamos o númerode árvores geradoras de alguns grafos circulantes, usando os re-sultados da Seção 2.3.1.

Exemplo 4.6. Número de árvores geradoras do grafo Mh (“MöbiusLadder”): Como Mh é um grafo 3-regular, usando o espectro deMh calculado no Exemplo 2.9, o Corolário 4.2 nos diz que onúmero de suas árvores geradoras é dado por

τ(Mh) =1

2h

2h−1∏k=1

(3− 2cos(kπ

h− (−1)k)).

Exemplo 4.7. Número de árvores geradoras do hiperoctaedroHs. Como Hs um grafo (2s− 2)-regular, usando o espectro cal-culado no Exemplo 2.10 e o Corolário 4.2, obtemos

τ(Hs) =1

2s

2∏i=1

(2s− 2− λi)mi =

=1

2s(2s− 2)s(2s)s−1 = 22s−2(s− 1)sss−2.


Para o último exemplo, precisamos dos seguintes lemas:

Lema 4.5. L(G) + L(G) = nI − J .

Demonstração:

L(G) + L(G) = D −A+D −A = D +D − (A+A) ,

onde D (respectivamente, D) é a matriz diagonal dos graus deG (respectivamente, G). Mas

D =

k1 0 0 ... 0

0 k2 0 ... 0...

......

......

0 0 0 ... kn

e

D =

n− (k1 + 1) 0 0 ... 0

0 n− (k2 + 1) 0 ... 0...

......

......

0 0 0 ... n− (kn + 1)

.

Logo,

D +D =

n− 1 0 0 ... 0

0 n− 1 0 ... 0...

......

......

0 0 0 ... n− 1

.

Sabemos ainda que A + A é a matriz com diagonal principaligual a zero e todas as outras entradas iguais a 1. Portanto,D +D − (A+A) = nI − J .


Lema 4.6. Seja σG(µ) = det(µI−L) o polinômio característicode L. Então

(i) Se G é desconexo, σG(µ) é o produto dos polinômios carac-terísticos das suas componentes conexas;

(ii) Se G é k-regular e pG(λ) é o polinômio característico de A

então σG(µ) = (−1)npG(k − µ);

(iii) τ(G) = n−2σG(n).

Demonstração: (i) Decorre da definição de polinômio caracterís-tico.

(ii) Neste caso, temos que L = kI −A. Logo

det(µI − L) = det(µI − (kI −A)) = det((µ− k)I +A) =

= (−1)ndet((k − µI −A) = (−1)npG(k − µ).

(iii) Pelo Lema 4.5, temos que L + L = nI − J . Pelo Corolário4.1,

τ(G) = n−2det(J + L) = n−2det(nI − L) = n−2σG(n).

Exemplo 4.8. Número de árvores geradoras do grafo multi-partido completo. Consideremos o grafo s-partido completo G =

Ka1,a2,...,as , onde a1, a2, . . . , as ∈ N com a1+a2+ . . .+as = n.Embora este grafo não seja necessariamente regular, seu com-plementar é: G consiste de s componentes conexas isomorfas aKa1

,Ka2, . . . ,Kas

. Usando (ii) do lema anterior, chegamos a

σKa(µ) = (−1)apKa(a− 1− µ)(−1)a(a− µa−1(−µ)) =

= [(−1)(a− µ)]a−1µ = µ(µ− a)a−1.

Consequentemente, aplicando (i) e (iii) do Lema 4.6, temos

τ(G = Ka1,a2,...,as) = n−2σG(n) = n−2s∏

i=1

σKai(n) =

= n−2n(n− a1)a1−1 . . . n(n− as)

as−1 =

= ns−2(n− a1)a1−1 . . . (n− as)

as−1.

Em particular, para grafos bipartidos completos temos τ(Ka,b) =

ba−1ab−1.

4.3 Conectividade algébrica

Definição 4.5. O segundo menor autovalor do Laplaciano deG, µn−1, é chamado conectividade algébrica do grafo G eserá denotado de agora em diante por a(G). O maior autovalordo Laplaciano de G, µ1, é chamado índice do Laplaciano deG.

A conectividade algébrica desempenha um papel funda-mental no estudo de um grafo. Este autovalor está associado adiferentes e importantes invariantes de grafos, tais como númeroisoperimétrico e diâmetro dentre outros. Foi comprovado recen-temente que grafos com conectividade algébrica grande (em com-paração com o grau máximo) têm propriedades importantes emvárias aplicações [70]. As Tabelas 1 e 2 apresentam os valores daconectividade algébrica de alguns grafos.

A próxima proposição estabelece uma relação entre aconectividade algébrica de um grafo e o índice do Laplaciano doseu complementar.

4.3 Conectividade algébrica 101

Grafo G Conectividade algébrica a(G)

Grafo completo a(Kn) = nCaminho a(Pn) = 2(1− cos π

n )Ciclo a(Cn) = 2(1− cos 2π

n )Grafo bipartido completo a(Kp,q) = min{p, q}

Estrela K1,q, q > 1 a(K1,q) = 1Cubo m-dimensional a(Cbm) = 2Grafo de Petersen a(P ) = 2

Tabela 1 – Alguns grafos para os quais a(G) é conhecido.

Operações a(G) e a(Gi), i = 1, 2

Grafo complementar G a(G) = n− µ1

G1 = G− {e}, e aresta de G a(G1) ≤ a(G)G1 = G− k vértices a(G) ≤ a(G1) + kG1 = G+ {e}, e aresta de G a(G) ≤ a(G1) ≤ a(G) + 2G = G1

∪G2 a(G) = a(G1) + a(G2)

G = G1 ×G2 a(G) = min{a(G1), a(G2)}

Tabela 2 – a(G′), para G′ um grafo obtido de G.

Proposição 4.3. Se o espectro do Laplaciano de um grafo G éζ(G) = (µ1, . . . , µn−1, 0) então o espectro de G é

ζ(G) = (n− µn−1, . . . , n− µ1, 0).

Demonstração: Já vimos que o vetor-coluna 1 é autovetor associ-ado ao autovalor 0 de L. Como L é uma matriz simétrica pode-mos tomar w1,w2, . . . ,wn−1 autovetores associados a µ1, µ2,

. . . , µn−1 respectivamente, de modo que wi seja ortogonal a 1,para todo i, 1 ≤ i ≤ n − 1. Assim, 1T .wi = 0, para todo i,1 ≤ i ≤ n − 1. Afirmamos que, para todo i, 1 ≤ i ≤ n − 1,wi é autovetor de G associado a n − µi. De fato, pelo Lema4.5, L(G) = nI − J − L(G) , onde J é a matriz quadrada de


entradas iguais a 1. Portanto, L(G)wi = (nI − J − L(G))wi =

nIwi−Jwi−L(G)wi = nwi−0−µiwi = (n−µi)wi , provandoassim o resultado.

Corolário 4.3. Seja ζ(G) = (µ1 , . . . , µn−1 0) o espectro doLaplaciano de um grafo G. Então µ1 ≤ n e µ1 = n se e somentese G é desconexo.

Demonstração: Como a(G) = n − µ1(G) e a(G) ≥ 0 temos queµ1(G) ≤ n. Além disso, G é desconexo se e somente se a(G) = 0.Portanto, G é desconexo se e somente se µ1(G) = n.

Exemplo 4.9. A estrela K1,n de n+1 vértices tem o índice doLaplaciano igual a n+1. Em particular, ζ(K1,6) = (7, 1, 1, 1, 1, 1, 0)

e ζ(K1,6) = (6, 6, 6, 6, 6, 0, 0) -vide Figura 31.

Figura 31 – A estrela K1,6 tem µ1 = 7.

É importante ressaltar que também é possível exibirgrafos não isomorfos que são coespectrais em relação à matrizLaplaciana, como mostra a Figura 32.

Veremos agora alguns limites superiores e inferiores paraa conectividade algébrica e o índice do Laplaciano, em função de

4.3 Conectividade algébrica 103

Figura 32 – Grafos Laplacianos-coespectrais não isomorfos.

outros parâmetros de grafos. Vamos inicialmente definir outrasmedidas de conectividade para um grafo.

Definição 4.6. A conectividade de vértices de um grafo,denotada por k(G), é o menor número de vértices que, ao seremretirados, tornam o grafo desconexo.

Definição 4.7. A conectividade de arestas, denotada pork′(G), é o menor número de arestas que, ao serem retiradas,tornam o grafo desconexo.

A conectividade algébrica e as conectividades de vérticese de arestas estão relacionadas de acordo com o resultado abaixo,provado por Fiedler [36].

Proposição 4.4. Se G não é o grafo completo então a(G) ≤k(G) ≤ k′(G) .

Como a conectividade de arestas é menor ou igual aograu mínimo de um grafo, podemos reescrever a Proposição an-terior como a(G) ≤ k(G) ≤ k′(G) ≤ δ(G).

Exemplo 4.10. O grafo da Figura 33 tem conectividade al-gébrica a = 0, 3820 e k = k′ = δ = 1 .



Kirkland et al. [60] caracterizaram os grafos G para osquais a(G) = k(G).

Proposição 4.5. Para todo grafo G, a(G) ≤ nn−1δ(G).

Demonstração: Temos que a(G) = min{vTLv;v ̸= 0,v ⊥ 1}(pelo Princípio de Rayleigh, ver Corolário 7.3). ConsideremosL̃ = L − a(I − 1

nJ), onde a = a(G). Verificamos que L̃.1 = 0.Dado y ∈ Rn, podemos escrever y = c11+ c2x, onde x ∈ {1}⊥

e ∥x∥ = 1. Logo yT L̃y = c22(xTLx − a) ≥ 0. Isto é, L̃ é uma

matriz semidefinida positiva, o que implica (L̃)ii ≥ 0, para todoi = 1, . . . , n e, portanto, (L)ii − a(1− 1

n ) = (L)ii − a(n−1n ) ≥ 0,

para todo i = 1, . . . , n. Como δ(G) = di, para algum i = 1, . . . , n,e di = (L)ii, a prova está completa.

Proposição 4.6. Para todo grafo G, nn−1∆(G) ≤ µ1(G) ≤

2∆(G).

Demonstração: A Proposição 4.5 usada para G fornece a(G) ≤n

n−1δ(G). A primeira desigualdade segue daí, fazendo-se as sub-stituições a(G) = n − µ1(G) e δ(G) = n − 1 − ∆(G). A outradesigualdade segue do fato de que µ1 = maxi µi. Em particular,

µ1 ≤ max1≤i≤n

∑nk=1 | Lik |= max1≤i≤n 2di = 2∆.

A conectividade algébrica está também relacionada como diâmetro do grafo através da desigualdade diam(G) ≥ 4

na(G)

[71]. Existem ainda alguns limites superiores para o diâmetro,também em função da conectividade algébrica.

Até 1990 supunha-se que, em qualquer coleção de ár-vores com o mesmo número de vértices, a conectividade algébricadecrescia conforme o diâmetro crescia. Grone e Merris [43] deramcontraexemplos para essa conjectura. Um deles é apresentado naFigura 34:

Figura 34 – Contraexemplo de Grone e Merris

4.4 Autovalores e o problema do corte maximal

Definição 4.8. Seja G = G(V,E) um grafo simples valoradode ordem n, onde V = {1, 2, ..., n} é o conjunto de vértices deG e E = {{i, j}|i, j ∈ V } o conjunto de arestas. Assim, a cada{i, j} ∈ E é atribuído um peso cij ∈ R. Um corte é um conjunto∂(S) = {{i, j}|i ∈ S, j /∈ S}, para algum S ⊂ V . O problematrata de achar um corte em G que maximize a seguinte função:

c(∂(S)) =∑

{i,j}∈∂(S)

cij .

O corte maximal de G, denotado por mc(G), é o número


definido por

mc(G) = maxS⊂V

c(∂(S)) = maxS⊂V

∑{i,j}∈∂(S)

cij = maxS⊂V

∑i∈V,j∈V−S

cij .

Se G é não valorado, os pesos são dados por

cij =

{1, se {i, j} ∈ E;

0, se {i, j} /∈ E.

Neste caso, o corte maximal de G é dado por

mc(G) = maxS⊂V

c(∂(S)) = maxS⊂V

| ∂(S) | .

Exemplo 4.11. Para os grafos G1 e G2 da Figura 35, temosque mc(G1) = 4 e mc(G2) = 6.

Figura 35 – Grafos do Exemplo 4.11.

No que se segue, considerando G um grafo valorado,L(G) = (Lij) é a matriz Laplaciana valorada de G definidaabaixo:

Lij =

−cij , se i ̸= j;n∑

k=1

cik, se i = j.

Lema 4.7. Seja G um grafo valorado e µ1(G), o índice do

Laplaciano L(G). Então mc(G) ≤ µ1| S | (n− | S |)

n, para todo

subconjunto S de vértices.

4.4 Autovalores e o problema do corte maximal 107

Demonstração: Temos que µ1 = maxx̸=0

xTLx

xTx(Princípio de Rayleigh,

Corolário 7.1). Dado S ⊂ V , defina x = [x1 x2 · · · xn]T por

xi =

{n− s, se i ∈ S;

−s, se i /∈ S,

onde s =| S | . Como xTLx =∑i,j∈E

cij(xi − xj)2 ,

∑i,j∈E

cij(xi − xj)2=

∑i,j∈∂(S)

cij(xi − xj)2=

= n2∑

i,j∈∂(S)

cij = n2c(∂(S))

e xTx = s(n− s)2 + (n− s)s2 = s(n− s)n ,

temos que µ1 ≥nc(∂(S))

s(n− s). Isto prova o resultado.


Exemplo 4.12. Para o grafo G da Figura 36 tem-se mc(G) = 4

e µ1 = 4. Para S = {v1, v2}, tem-se então que 4 ≤ 42.57 .

Teorema 4.3. Seja G um grafo valorado. Então mc(G) ≤ µ1n4 .

Demonstração: É fácil verificar que são verdadeiras as seguintesequivalências:

(n− 2s)2 ≥ 0⇔ n2 − 4s(n− s) ≥ 0⇔ s(n− s) ≤ n2

4.


Logo, pode-se concluir que

nc(∂(S)) ≤ µ1s(n− s) ≤ µ1n2

4.

Isto implica em c(∂(S)) ≤ µ1n4 . Portanto,

maxS⊂V

c(∂(S)) ≤ µ1n

4.

Exemplo 4.13. Para o grafo do Exemplo anterior (Figura 36),temos

maxS⊂V

c(∂(S)) = 4 ≤ 47

4= µ1

n

4.

4.4.1 Corte maximal e autovalores em certos grafos

Para algumas classes especiais de grafos, os limites su-periores para o corte maximal são obtidos a partir do índice doLaplaciano:

• grafos completos: µ1(Kn) = n e mc(Kn) =n2

4 = nn4 .

• grafos bipartidos r-regulares: µ1(G) = 2r e mc(G) = 2rn4 .

No que se segue apresentaremos algumas classes de grafosnas quais o limite superior obtido no Teorema 4.3 é atingido.

Definição 4.9. Diremos que um grafo G de ordem par é exatoquando mc(G) = µ1

n4


Alguns exemplos de grafos exatos, com possíveis re-strições sobre a paridade de alguns parâmetros, são: grafos com-pletos, grafos bipartidos r-regulares, ℓ(K4k+1) e o complementarde ℓ(Km,n).

Definição 4.10. Um grafo é dito semirregular quando cadaum dos seus vértices está a uma distância igual a 2 do mesmonúmero de vértices.

Note-se a analogia com a noção de grafo regular, ondecada vértice está a uma distância igual a 1 do mesmo número devértices.

Proposição 4.7. Seja G um grafo bipartido (r, s)-semirregularonde r e s são pares. Então ℓ(G) é exato.

Demonstração: O conjunto de arestas E(G) de G pode ser de-composto em dois subgrafos (r, s)-semirregulares que formamuma bipartição ótima de ℓ(G).

Proposição 4.8. Seja n ≤ m, n par. Então ℓ(Km,n) é exato.

Demonstração: Temos que µ1(ℓ(Km,n)) = n(m − 1). O cortemaximal é obtido por ∂({{i, j}|i = 1, . . . , n

2 , j = 1, . . . ,m}).

Proposição 4.9. ℓ(K4k+1) é exato.

Demonstração: ℓ(K4k+1) possui um fator 2r-regular, que é ocorte maximal no grafo-linha.


Introduziremos a seguir o número φ(G), definido paracada grafo valorado G, que, como mostraremos, é sempre umlimite superior para o corte maximal mc(G).

Definição 4.11.

φ(G) = minΣuj=0

1

4nµmax(L+ U) ,

onde U = diag(u1, u2 . . .), µmax é o autovalor máximo damatriz L + U e o mínimo é tomado sobre todos os vetores u =

[u1 u2 · · · un]T ∈ Rn satisfazendo

∑ui = 0. A cada vetor u tal

que∑

ui ≥ 0 chamamos um vetor corretor (a entrada ui estáassociada ao vértice i de G).

Lema 4.8. Temos que mc(G) ≤ 14nµmax(L+U), para todo vetor

corretor u.

Demonstração: Dado S ⊂ V , defina x = [x1 x2 · · · xn]T por

xi =

{1, se i ∈ S;

−1, se i /∈ S.

Então,

xTLx =∑

{i,j}∈E

cij(xi − xj)2 = 4

∑i∈S,j /∈S

cij .

Mas, xTUx =∑

uixi2 =

∑ui ≥ 0. Se S induz o corte maximal,

4mc(G) = xTLx ≤ xT (L + U)x, para qualquer vetor corretoru. Aplicando o Princípio de Rayleigh (Corolário 7.1) ao vetor x,4mc(G) ≤ xT (L+ U)x ≤ nµmax(L+ U)

Lema 4.9. A função φ da Definição 4.11 é tal que:


(i) Se cada cij é multiplicado por algum real k positivo, φ étambém multiplicado por k (φ é homogênea positiva);

(ii) Se G e G′ possuem os mesmos vértices e funções pesos c ec′, satisfazendo cij ≤ c′ij para todo par de vértices, entãoφ(G) ≤ φ(G′) (φ é monótona).

Demonstração: (i) Seja G′ o grafo com função peso c′ tal quec′ij = kcij . Então

xTLG′x = kxTLGx e

xT (LG′ + kU)x = xTLGx+ kxTUx = kxT (LG + U)x.

Para todo x autovetor de LG + U associado a µmax(LG + U)

temos

xT (LG′ + kU)x

xTx=

kxT (LG + U)x

xTx= kµmax(LG + U).

Para todo x autovetor de LG′ +kU , associado a µmax(LG′ +kU)

temos

kxT (LG + U)x

xTx=

xT (LG′ + kU)x

xTx= µmax(LG′ + kU).

Logoµmax(LG′ + kU) = kµmax(LG + U).

Daí,

minku

1

4nµmax(LG′ + kU) = min

u

1

4nµmax(LG′ + U) =

= kminu

1

4nµmax(LG + U).

(ii) Para todo vetor x, temos

xTLGx =∑

cij(xi − xj)2 ≤

∑c′ij(xi − xj)

2 ≤ xTLG′x.


Isto acarretaxT (LG′ − LG)x ≥ 0.

Se x é autovetor de LG′ + U , U = diag(u1, . . . , un) qualquer,

xT (LG + U)x

xTx≤ xT (LG′ + U)x

xTx= µmax(LG′ + U).

Se x é autovetor de LG + U ,

µmax(LG + U) =xT (LG + U)x

xTx≤ µmax(LG′ + U).

Observe que um limite superior trivial para mc(G) é asoma de todos os pesos não negativos das arestas.

Teorema 4.4. Seja G um grafo valorado com função peso c.Então, φ(G) ≤

∑ce≥0

ce.

Demonstração: Seja c′ij = max(0, cij), para todos pares de vér-tices e seja G′ o grafo valorado correspondente. Como φ(G) ≤φ(G′), podemos assumir que c é não negativo. Seja m =

∑cij , e

considere o vetor corretor definido por ui =4mn − 2

∑j cij . Para

todo x = [x1 · · · xn]T ,

xT (L+ U)x =∑

cij(xi − xj)2 +

∑i

uix2i =

=∑

cij(xi + xj)2 +

∑i

(4m

n− 2

∑j

cij)x2i

=4m

nxTx−

∑cij(xi + xj)

2 ≤ 4m

nxTx.

Se x é o autovetor associado ao maior autovalor µmax de L+U ,xT (L+U)x = µmax(L+U)xTx ≤ 4m

n xTx. Daí, µmax(L+U) ≤

4mn e φ(G) ≤ m.


Exemplo 4.14. Considere o grafo da Figura 37. Temos n = 3,mc(G) = 2 e µ1(G) = 3. Pelo Teorema 4.3, obtemos o seguintelimite superior para mc(G): mc(G) ≤ 33

4 = 2, 5.

Usando o vetor corretor construído na prova do Teo-rema 4.4, temos: m = 2; u1 = 2

3 ; u2 = − 43 ; u3 = 2

3 e µmax(L+

U) = 249 . Nesse caso o limite superior coincide com mc(G):

249

34 = 2.

Observe que a prova do Teorema 4.4 nos indica umaboa escolha para o vetor corretor. Certamente uma escolha in-adequada do vetor corretor pode resultar num limite ruim.

Exemplo 4.15. Considere a estrela Sn = K1,n−1 com o vetorcorretor nulo. Então

1

4nµmax(L+ U) =

1

4nµ1(L) =

1

4n2 ,

enquanto mc(Sn) = n− 1 = φ(Sn). Para S4 temos

1

44µ1(L) =

1

416 = 4.

Se considerarmos u = [−3, 1, 1, 1]T teremos

1

44µmax(L+ U) =

1

44.3 = 3 = mc(S4).


4.5 Aplicações

Nesta seção veremos algumas importantes aplicações daTeoria Espectral de Grafos à Química e à Biologia. Usaremos aconectividade algébrica e o índice do Laplaciano de grafos asso-ciados a moléculas e analisaremos o tipo de informação obtidaatravés desses parâmetros, em cada caso.

4.5.1 Carbonos quaternários e grau máximo

Uma árvore com grau máximo menor ou igual a 4 éum grafo molecular representando isômeros de alcanos (se n é onúmero de vértices o grafo representa um isômero de CnH2n+2).Temos que ∆ = 1 é satisfeito apenas pelo etano e ∆ = 2 é satis-feito apenas pelos isômeros de cadeia linear (normal) de alcanos,ou seja, sem ramificações. Temos ainda que ∆ = 3 indica que amolécula possui apenas carbonos terciários e, finalmente, ∆ = 4

indica a presença de pelo menos um carbono quaternário.

A partir da desigualdade abaixo, estabelecida em [46] eque relaciona grau máximo e maior autovalor do Laplaciano,

∆+ 1 < µ1 < ∆+ 1 + 2√∆− 1,

conhecendo µ1 podemos detectar a presença de carbono quater-nário.

Na Figura 38, onde apresentamos as árvores químicasdos isômeros do octano, observamos a presença de carbonosquaternários (correspondendo a △ = 4), nos casos em que µ1 >

5.

4.5 Aplicações 115

Figura 38 – Isômeros do octano: m1 é o índice do Laplaciano.

4.5.2 RNA e conectividade algébrica

Este exemplo pode ser encontrado em [59]. O dobra-mento da molécula de RNA mensageiro forma estruturas se-cundárias e terciárias. Por exemplo, consideremos um RNA men-


sageiro de fita simples, cuja sequência de bases nitrogenadas édada por

C G C U C U G U U U A C C A G G U C A G G UC C G A A A G G A A G C A G C C A A G G C A G A G CC C C C

G

A A

A

C G

C

U

G

A G

G

A

C U

A

G

G

C

A

G

G

C

C A

C

C

A U A

A

U G

U G

G C

U A

C G

U A

C G

G C

G C

C

C

*

40

20

A

B

C

D

Figura 39 – Estrutura secundária do RNA

A estrutura secundária é dada na Figura 39 e corre-

4.5 Aplicações 117

sponde ao grafo da Figura 40.

Figura 40 – Grafo da estrutura secundária do RNA.

Figura 41 – Árvores de ordem 8 e conec. alg. crescentes.

Moléculas de RNA biologicamente correlacionadas ten-dem a ter estruturas secundárias similares. Portanto, comparargrafos de RNA pode ser útil para identificar moléculas de RNA

que são estruturalmente, funcionalmente ou evolutivamente cor-relacionadas. O segundo menor valor do Laplaciano (conectivi-dade algébrica) é uma medida de compacidade do grafo: conec-

tividade algébrica grande indica um grafo compactado, enquantoconectividade algébrica pequena indica que o grafo é alongado.

As árvores da Figura 41 ilustram a relação entre conec-tividade algébrica e a estrutura do grafo. Em todas elas, a conec-tividade de vértices e a conectividade de arestas são iguais a 1;apenas a conectividade algébrica varia, correspondendo às diver-sas topologias destas árvores.

4.5.3 Potencial de ionização

Em Química encontramos algumas aplicações da matrizLaplaciana e seu espectro. Artigos recentes têm explorado a lig-ação entre Teoria Espectral de Grafos e propriedades químicas.Em [46], Gutman, Vidović e Stevanović afirmam que o maiorautovalor do Laplaciano de um grafo molecular é um parâmetroimportante no estudo do espectro fotoeletrônico dos hidrocar-bonetos saturados. O potencial de ionização dos alcanos é ex-presso por α+ (µi − 2)β, 1 ≤ i ≤ n, onde α e β são constantesempíricas e (µ1, . . . , µn) é o espectro do Laplaciano. Assim, omaior autovalor do Laplaciano representa o primeiro potencialde ionização do respectivo alcano.

4.6 Exercícios

1. Determine o espectro do grafo e o espectro da matriz Lapla-ciana do grafo G da Figura 42.

2. Determine os espectros da matriz de adjacência e da matrizLaplaciana do grafo G da Figura 43. Em que classe especialde grafos ele se encaixa?

4.6 Exercícios 119

Figura 42 – Grafo do Exercício 1.

Figura 43 – Grafo do Exercício 2.

3. Um grafo é autocomplementar se ele é isomorfo ao seucomplementar. Mostre que ℓ(K3,3) é autocomplementar.Determine os autovalores de K3,3 e de seu Laplaciano.

4. Mostre que todo grafo G com conectividade de vérticesκ(G) = 2 contém um ciclo.

5. Mostre que se T é uma árvore com pelo menos 3 vérticesentão a(G) ≤ 1. Mostre também que a igualdade é vál-ida somente se a árvore é uma estrela, ou seja, um grafoisomorfo a K1,n.

6. Seja e uma aresta de um grafo G. Prove que a(G−{e}) =a(G)− 2 se e somente se G = Kn.

7. Determine a conectividade algébrica de C5 e P5. Qual delasé a maior? Suponha que cada um desses grafos modele umarede que liga 5 computadores num pequeno laboratóriouniversitário. Qual das duas redes é menos vulnerável com

120 Matriz Laplaciana de um grafo

relação à interrupção da comunicação entre os computa-dores?

8. Considere um grafo G cuja sequência de graus é dada pord(G) = [2, 3, 4, 4, 3, 2]. Desenhe um grafo com esta se-quência de graus e calcule a sua conectividade algébrica.Este grafo tem o ciclo C6 como seu subgrafo? Dê a conec-tividade algébrica desse ciclo. Qual dos grafos tem maiorconectividade algébrica? Se ambos modelassem uma rede,qual delas seria mais vulnerável?

9. Seja B a matriz de incidência de um grafo G e para umaorientação qualquer de G, seja β a matriz de incidênciado grafo orientado. Prove que G é bipartido se e somentese exitir uma matriz diagonal M com entradas ±1 tal queMβ = B.

10. Seja G o grafo cubo dado na Figura 25. Determine as ma-trizes de incidência B e β, essa última com respeito a umaorientação atribuída arbitrariamente. Como já vimos, esseé um grafo bipartido, logo existe uma matriz diagonal Mtal que Mβ = B. Determine M .

11. Seja o grafo G dado na Figura 42. Dê uma orientação o1

para G e determine a matriz de incidência βo1 correspon-dente a essa orientação. Atribua uma outra orientação o2

para G e determine βo2 . Verifique se βTo1βo1 = βT

o2βo2 . Seráeste um resultado que vale para qualquer grafo G? Parauma resposta afirmativa, prove o resultado. Em caso con-trário, apresente um contraexemplo.

12. Grafos com a mesma sequência de graus sempre têm po-linômios característicos iguais e polinômios característicos

dos seus Laplacianos também iguais? Justifique sua res-posta.


Para este capítulo dedicado à matriz Laplaciana, cabeuma nota sobre um livro bem conceituado entre pesquisadoresque aplicam a técnica espectral de grafos em Ciência da Com-putação. A autora é F. Chung [19], que introduz o conceito deLaplaciano normalizado de um grafo. Muitos resultados, quandodecorrentes da definição de matriz Laplaciana usual aqui es-tudada, são válidos somente para grafos regulares. Segundo aautora, a vantagem de se adotar o conceito da matriz Lapla-ciana normalizada é que os resultados podem ser estendidos paragrafos em geral. No entanto, o livro de Chung não é recomendadopara estudantes que estejam se iniciando na área. Novamente, in-dicamos os livros de Teoria Algébrica e/ou Espectral de Grafos,citados nas Notas Bibliográficas do Capítulo 2, com destaquepara os livros do Godsil & Royle [41] e Beineke & Wilson [8].Ambos têm capítulos especiais dedicados à matriz Laplaciana deum grafo.

Vale relatar aqui também, que mais de vinte anos apóster introduzido o conceito de energia de um grafo, I. Gutman,juntamente com B. Zhou, estabeleceu em 2006, em [48], um con-ceito de energia em termos dos autovalores da matriz Laplaciana.O novo conceito foi concebido de modo a preservar certas pro-priedades análogas às do invariante original. De lá para cá, aspropriedades da energia Laplaciana têm sido objeto de estudode muitos pesquisadores. Para maiores detalhes, além do artigo

122 Matriz Laplaciana de um grafo

original, recomendamos [83], pela lista de referências que con-tém.

A conectividade algébrica, tratada aqui de modo su-perficial, tem uma importância grande tanto do ponto de vistateórico quanto do ponto de vista de aplicações. Em particular,o autovetor associado à conectividade algébrica, chamado vetorde Fiedler [36], desempenha um papel importante, cujas impli-cações teóricas e práticas estão impressas em centenas de artigosencontrados em dezenas de periódicos de várias áreas. Nas sur-veys [1, 3] é possível encontrar um guia para a literatura.

5 Matriz Laplaciana sem sinal

O estudo dos coeficientes e das raízes dos polinômioscaracterísticos das matrizes de adjacência e Laplaciana de umgrafo tem recebido muita atenção dos pesquisadores, como jávimos nos capítulos especialmente dedicados a tais matrizes.No entanto, dado que estes polinômios não são suficientes parafornecer invariantes de grafos capazes de caracterizá-los, nemmesmo nos casos mais simples como as árvores, o estudo de out-ras matrizes relacionadas a um grafo merece também a nossaatenção. Assim, vamos apresentar neste capítulo a matriz Lapla-ciana sem sinal, que só mais recentemente despertou interessedos pesquisadores.

5.1 Matriz Laplaciana sem sinal

A matriz Laplaciana sem sinal, via espectro e invariantesdele derivados, embora não seja suficiente para permitir a carac-terização de grafos, parece garantir a existência de um númeromuito maior de grafos que podem ser caracterizados pelo seuespectro que a Laplaciana, que por sua vez parece mostrar-semais eficiente que a matriz de adjacência no auxílio à realizaçãodesta tarefa, [30] e [84]. De acordo com Cvetković [30], simu-lações feitas por Dam e Hammers [32] confirmam tais suspeitas.Além disso, Zhu e Wilson [84] estenderam as simulações de Dame Hammers [32], confirmando que o espectro da matriz Lapla-ciana sem sinal é mais eficaz no reconhecimentos de grafos, se


comparado ao espectro da matriz de adjacência e, até mesmo, daLaplaciana, dentre outras matrizes por eles testadas, [4] e[30].

Definição 5.1. A matriz Laplaciana sem sinal de um grafoG é dada por Q = D + A, onde D é a matriz diagonal cujasentradas são os graus dos seus vértices e A é a sua matriz deadjacência. O polinômio característico da matriz Lapla-ciana sem sinal é denotado por pQ(λ) e seus autovalores sãodenotados por q1 ≥ q2 ≥ · · · ≥ qn, sendo q1 o índice de Q.

Observação 5.1. A matriz Laplaciana sem sinal Q(G) é simétricae tem as entradas não-negativas, como a matriz de adjacência.Além disso, se G for conexo, esta matriz é também irredutível.Podemos então usar novamente o Teorema de Perron-Frobenius7.4, como em relação à matriz A(G), obtendo que, para grafosconexos, q1 é autovalor simples.Notamos ainda que q1 = 0 se, e somente se, G é um grafo semarestas.

De acordo com a definição acima, se nos reportarmos aoCapítulo 3, veremos que a matriz Laplaciana sem sinal já é nossaconhecida. Do Lema 3.2, ela é exatamente a matriz BBT , ondeB é a matriz de incidência associada a um grafo não orientado.Também vimos, no Lema 3.1, que vale a seguinte equação ma-tricial para um grafo G com m arestas: BTB = 2Im +A(ℓ(G)),onde Im é a matriz identidade de ordem m e A(ℓ(G)) é a matrizde adjacência do grafo-linha de G.

O resultado a seguir mostra a relação entre os polinô-mios característicos da matriz de adjacência do grafo-linha e damatriz Laplaciana sem sinal de um grafo.

5.1 Matriz Laplaciana sem sinal 125

Proposição 5.1. Seja G um grafo com n vértices e m arestas,ℓ(G) o seu grafo-linha e Q a sua matriz Laplaciana sem sinal.Temos que pℓ(G)(λ) = (λ+ 2)m−npQ(λ+ 2).

Demonstração: Sejam A(G) a matriz de adjacência de G, B

sua matriz de incidência e D(G) a matriz diagonal dos graus deseus vértices. A prova decorre das seguintes identidades BBT =

A(G) +D(G) e BTB = A(ℓ(G)) + 2Im, oriundas dos Lemas 3.1e 3.2, lembrando que BBT e BTB têm os mesmos autovaloresnão nulos, com as mesmas multiplicidades, pela Proposição 7.1.

Tal como ocorre com a matriz de adjacência, é possívelexpressar o número de arestas de um grafo em função de um doscoeficientes de pQ(λ), como nos diz a próxima proposição.

Proposição 5.2. O número de arestas de um grafo G com n

vértices é igual a−p12

, onde p1 é o coeficiente de λn−1 no poli-nômio característico de Q.

Demonstração: O traço da matriz Laplaciana sem sinal é a somados graus dos vértices de G, que por sua vez é 2m, onde m é onúmero de arestas de G. Pelo mesmo resultado de teoria de ma-trizes utilizado na demonstração de 2.1, este valor é também asoma das raízes do polinômio característico de Q e o valor −p1do coeficiente do termo λn−1 deste polinômio. Assim, m = −p1

2 .

A Proposição 5.3 dá um limite superior e outro inferiorpara o índice de Q(G) em função dos graus dos vértices de G.

Proposição 5.3. Seja G um grafo com n vértices e m arestas,cuja sequência de graus é dada por d1 ≥ d2 ≥ · · · ≥ dn. Para


todos vi e vj vértices adjacentes em G, min{di + dj} ≤ q1 ≤max{di + dj}.

Demonstração: O grafo-linha ℓ(G) de G tem seu máximo auto-valor igual a q1 − 2, pela Proposição 5.1. Seja eij uma aresta deG cujos vértices terminais são vi e vj . Faça u ser o vértice deℓ(G) correpondente à aresta eij . É lógico que o grau de u é iguala di + dj − 2. Então, pela Proposição 2.4, temos que

min{di + dj − 2} ≤ q1 − 2 ≤ max{di + dj − 2}.

Daí segue o resultado.

Como consequência imediata desta proposição, temoscotas superior e inferior para o índice de Q(G), em função do graumáximo e do grau mínimo de G, em analogia ao que acontececom a matriz de adjacência, como visto na Proposição 2.4, usadana prova acima.

Corolário 5.1. 2δ ≤ q1(G) ≤ 2∆.

Veremos agora dois resultados sobre o Q-espectro degrafos bipartidos.

Proposição 5.4. Para grafos bipartidos, o espectro da matrizLaplaciana sem sinal é igual ao espectro da Laplaciana, ou seja,para todo i, 1 ≤ i ≤ n, qi = µi.

Demonstração: Como G é bipartido, seu conjunto de vérticespode ser particionado em dois subconjuntos V1 e V2 tais que sedois vértices são adjacentes então eles estão em subconjuntos dis-tintos. Seja U a matriz diagonal com uii = 1, se vi ∈ V1 e uii =

5.1 Matriz Laplaciana sem sinal 127

−1, se vi ∈ V2. Temos que U é invertível com U−1 = U . SejamA, a matriz de adjacência, e D a matriz diagonal dos graus dosvértices de G. Sendo D e U ambas matrizes diagonais, elas comu-tam entre si. Além disso, é fácil mostrar que UAU−1 = −A (estaigualdade foi deixada como exercício no capítulo 2). A partirdaí, temos que ULU−1 = U(D−A)U−1 = UDU−1−UAU−1 =

UU−1D − UU−1A = D − (−A) = D + A = Q. Logo, L e Q

são matrizes semelhantes e, por isso, seus polinômios caracterís-ticos são iguais. Consequentemente, elas têm o mesmo espectro.

Para todo grafo G, sabemos que a matriz LaplacianaL(G) é uma matriz positiva semidefinida e singular. Consequente-mente, µn = 0. Embora Q seja também positiva semidefinida,ela não é necessariamente singular. Isso só acontece quando G éum grafo bipartido, como podemos ver na próxima proposição.

Proposição 5.5 ([30]). A matriz Laplaciana sem sinal de umgrafo G é singular se e somente se G é um grafo bipartido.

Demonstração: Se Q é singular então Q tem um autovalor nulo.Mas, da Proposição 5.1, 0 é autovalor de Q implica que −2 éautovalor de ℓ(G) com multiplicidade pelo menos m − n + 1,onde n é a ordem de G e m é o número de suas arestas. Daí, oTeorema 2.2.4 de [29] garante que G é bipartido. No outro sen-tido, suponhamos que G é bipartido. Segue da Proposição 5.4que qn = µn = 0. Logo, det(Q) = 0.

Para os grafos regulares, a Proposição 5.6, que pode serencontrada em [30], mostra que o espectro da matriz Laplacianasem sinal pode ser determinado tanto a partir do espectro da


matriz de adjacência de G como da sua matriz Laplaciana. Istoé muito interessante, pois com este resultado, toda a teoria jádesenvolvida para as matrizes de adjacência e Laplaciana podeser diretamente transferida para a Laplaciana sem sinal, pelomenos para os grafos regulares.

Proposição 5.6. Sejam G um grafo regular de grau r, L suamatriz Laplaciana e Q sua matriz Laplaciana sem sinal. Temosque pG(λ) = pQ(λ+ r) e σG(λ) = (−1)npQ(2r− λ), onde σG(λ)

indica o polinômio característico de L.

Demonstração: Para provar a primeira equação é suficiente lem-brar que D = rI e, portanto, A = Q−rI. Para provar a segunda,basta recordarmos que L = 2D −Q = 2rI −Q.

Temos ainda que os graus e o número de componentesconexas de um grafo regular podem ser determinados do poli-nômio característico da matriz Laplaciana sem sinal do grafo,conforme a Proposição 5.7, [28].

Proposição 5.7. Seja G um grafo com n vértices e m arestas.Então G é regular se e somente se nq1 = 4m. Neste caso, osgraus de seus vértices são iguais a

q12

e o número de componentesé a multiplicidade de q1.

Demonstração: Seja G um grafo conexo r−regular. Da Proposição2.7, temos que r é o índice de G e este é um autovalor simplesdo grafo. Sendo G regular,

m =nr

2. (5.1.1)

5.2 Q-espectro da união, produto cartesiano e “join” 129

Da Proposição 5.6, q1 = 2r e este é um autovalor simples de Q.Ao substituirmos r = q1

2 na equação 5.1.1, temos 4m = nq1. Onúmero de componentes decorre de que para um grafo regularconexo, q1 é um autovalor simples de G.

5.2 Q-espectro da união, produto cartesiano e “join”

Obteremos o Q-espectro do grafo resultante da união,do produto cartesiano e do join a partir dos espectros dos grafosusados na operção. Para as duas primeiras operações temos re-sultados gerais.

Proposição 5.8. Sejam G1 e G2 grafos com Q-autovaloresq1,1, . . . , q1,n e q2,1, . . . , q2,k, respectivamente.

1. Os Q-autovalores de G1∪G2 são q1,1, . . . , q1,n, q2,1, . . . , q2,k;

2. Os Q-autovalores de G1 ×G2 são q1,i + q2,j, i = 1, . . . , n,j = 1, . . . , k.

Demonstração: Seja Q(Gi) a matriz Laplaciana sem sinal de Gi,para i = 1, 2. Então:

1. Q(G1 ∪G2) =

[Q(G1) 0

0 Q(G2)

]e, portanto, seus auto-

valores são q1,1, . . . , q1,n, q2,1, . . . , q2,k ;

2. Q(G1×G2) =

Q(G2) + d1Ik a12Ik · · · a1nIk

a21Ik Q(G2) + d2Ik · · · a2nIk...

.... . .

...an1Ik an2Ik · · · annIk


= Q(G1) ⊗ Ik + In ⊗ Q(G2), onde ⊗ indica o produtode Kronecker das matrizes envolvidas. Então, por resul-tado de Teoria de Matrizes, seus autovalores são q1,i+q2,j ,i = 1, . . . , n, j = 1, . . . , k ([69]).

No próximo resultado, provado em [33], determinamoso Q-polinômio do grafo G1 ∨ G2, quando Gi é ri-regular, i = 1e 2, assim como no caso da matriz de adjacência,.

Teorema 5.1. Seja Gi um grafo regular de grau ri com ni vér-tices, para i = 1, 2,. Então o polinômio característico da matrizQ(G1 ∨G2) é dado por

PQ(G1 ∨G2, x) =PQ(G1, x− n2)PQ(G2, x− n1)

(x− 2r1 − n2)(x− 2r2 − n1)f(x),

onde f(x) = x2−(2(r1+r2)+(n1+n2))x+2(2r1r2+r1n1+r2n2).

Demonstração: Seja Gi um grafo regular de grau ri com ni vér-tices, i = 1, 2. Considere H

(i)1 , . . . ,H

(i)ki

as componentes conexasde Gi, |H(i)

j | = N(i)j e Q(H

(i)j ) = Q

(i)j , j = 1, . . . , ki. Então, a

matriz Laplaciana sem sinal do grafo G1∨G2 pode ser represen-tada na forma

Q = Q(G1 ∨G2) =

[Q(G1) + n2In1 Jn1,n2

Jn2,n1 Q(G2) + n1In2

],

onde

5.2 Q-espectro da união, produto cartesiano e “join” 131

Q(G1) =

Q

(1)1 + n2IN(1)

1· · · 0

. . .

0 · · · Q(1)k1

+ n2IN(1)k1

e

Q(G2) =

Q

(2)1 + n1IN(2)

1· · · 0

. . .

0 · · · Q(2)k2

+ n1IN(2)k2

.

Para j ∈ {1, . . . , k1}, se v satisfaz Q(1)j v = qv, com

q ̸= 2r1, então v é ortogonal a 1N

(1)j

e

w = [0T

N(1)1

, · · · ,vT , · · · ,0T

N(1)k1

,0Tn2]T

é tal que

Qw = (q + n2)w.

Analogamente, para j ∈ {1, . . . , k2}, se u é tal que Q(2)j u

= qu, com q ̸= 2r2, então u é ortogonal a 1N

(2)j

e

z = [0Tn1,0T

N(2)1

, · · · ,uT , · · · ,0T

N(2)k2

]T

satisfaz

Qz = (q + n1)z.

Agora, aplicando o Teorema 7.2 à matriz Q, obtemos


que todos os autovalores de

M =

2r1 + n2 · · · 0 N(2)1 · · · N

(2)k2

. . ....

...0 · · · 2r1 + n2 N

(2)1 · · · N

(2)k2

N(1)1 · · · N

(1)k1

2r2 + n1 · · · 0...

.... . .

N(1)1 · · · N

(1)k1

0 · · · 2r2 + n1

são autovalores de Q.

Uma vez que o polinômio característico de M é

p(x) = (x− 2r1 − n2)k1−1(x− 2r2 − n1)

k2−1f(x),

onde f(x) = x2−(2(r1+r2)+(n1+n2))x+2(2r1r2+r1n1+r2n2),

obtemos o resultado desejado.

5.3 Grafos Q-integrais

Uma das vertentes importantes na pesquisa em Teo-ria Espectral de Grafos é a busca por grafos integrais, isto é,grafos cujos autovalores são todos números inteiros. Em 1973,Harary e Schwenk publicaram o artigo Which graphs have inte-gral spectra?,[51], despertando o interesse por este tipo de grafo.Eles observaram que uma caracterização geral destes grafos pare-cia um problema intratável e, desde então, a busca por grafosintegrais se dá através de classes especiais de grafos. Mais tarde,em 1994, Grone e Merris, [44] estudaram os grafos Laplaciano in-tegrais, isto é, aqueles com espectro relativo à matriz Laplaciana

5.3 Grafos Q-integrais 133

formado exclusivamente por inteiros. Neste trabalho, eles desta-cam que parece existir mais grafos Laplaciano-integrais do queintegrais. Só mais recentemente, o problema análogo para matrizLaplaciana sem sinal tem sido abordado, como por exemplo em[76], [75] e [33]. Como aplicação dos resultados da seção anterior,veremos a seguir, alguns resultados sobre grafos Q-integrais, istoé, grafos cujo Q-espectro é formado apenas por inteiros.

O primeiro resultado, corolário imediato da Proposição5.6, relaciona os grafos integrais, Laplaciano integrais e Q-integrais.

Corolário 5.2. (5.6) Seja G grafo r-regular. G é integral ⇐⇒G é Laplaciano integral ⇐⇒ G é Q-integral.

Exemplo 5.1. Os grafos completos, como são regulares, fornecemuma coleção infinita de grafos que são simultaneamente integrais,Laplacianos integrais e Q-integrais. O Q-espectro do grafo Kn éSp (Q(Kn)) = (2n− 2, (n− 2)(n−1)).

O próximo resultado, consequência imediata da Proposição5.8, garante que as operações de união e produto cartesianopreservam Q-integralidade.

Corolário 5.3. Sejam G1 e G2 grafos Q-integrais. Então G1 ×G2 e G1 ∪G2 são Q-integrais.

No próximo resultado, consequência de 5.1 estabelece-mos condições necessárias e suficientes para que o join de grafosregulares seja Q-integral.

Corolário 5.4. Se Gi, i = 1, 2, é um grafo regular de grau ri

com ni vértices, então G1 ∨G2 é Q-integral se, e só se, G1 e G2

são Q-integrais e a expressão ((2r1−n1)− (2r2−n2))2 +4n1n2

é um quadrado perfeito.


Demonstração: Segue do teorema anterior que G1 ∨ G2 é Q-integral se, e só se, G1 e G2 são Q-integrais e as raízes de

f(x) = x2 − (2(r1 + r2) + (n1 + n2))x+ 2(2r1r2 + r1n1 + r2n2)

são inteiras. Assim, G1∨G2 é Q-integral se, e só se, G1 e G2 sãoQ-integrais e

(2r1 + 2r2 + n1 + n2)

2+

±√

(2r1 + 2r2 + n1 + n2)2 − 8(2r1r2 + r1n1 + r2n2)

2

são números inteiros.

Uma vez que 2r1 + 2r2 + n1 + n2 e (2r1 + 2r2 + n1 +

n2)2 − 8(2r1r2 + r1n1 + r2n2) têm a mesma paridade, para que

as raízes de f(x) sejam inteiras é necessário e suficiente que(2r1 + 2r2 + n1 + n2)

2 − 8(2r1r2 + r1n1 + r2n2) = ((2r1 − n1)−(2r2 − n2))

2 + 4n1n2 seja um quadrado perfeito.

Exemplo 5.2. O grafo K5 ∨K9, da Figura 44 é Q-integral.

Figura 44 – K5 ∨K9 é um grafo Q-integral

Observação 5.2. Se G1 e G2 são grafos regulares Q-integraisde mesmo grau r, então G1 ∨G2 é Q-integral pois ((2r − n1)−(2r − n2))

2 + 4n1n2 = (n1 + n2)2.

Através dos dois corolários anteriores, podemos con-struir novos grafos Q-integrais, partindo de grafos Q-integraisconhecidos. Temos ainda que, para grafos regulares, o comple-mentar de um grafo Q-integral é Q-integral (a prova desta afir-mação será deixada como exercício). Mas, ao contrário da matrizLaplaciana, o complementar de um grafo Q-integral pode não serQ-integral.

Exemplo 5.3. A Figura 45 mostra o grafo Q-integral G e seucomplementar G, cujos Q-espectros são Sp (Q(G)) = (5, 4, 2, 1(3))

e Sp (Q(G)) = ( 7+√17

2 , 3(3), 7−√17

2 , 0).

Figura 45 – G é Q-integral mas G não é.

5.4 Coespectralidade e aplicações

O espectro de um grafo é largamente utilizado em teo-ria dos grafos para caracterizar suas propriedades estruturais. Noentanto, o espectro não tem sido muito empregado quando se de-seja associar e/ou comparar dois desses grafos. Há duas fortes


razões para isso. A primeira é que, como já vimos, dois ou maisgrafos podem compartilhar o mesmo espectro e a segunda, é queo espectro muda drasticamente com uma pequena troca feita nografo, por exemplo, inserção, troca ou retirada de uma ou maisarestas e/ou de vértices. Embora esses fatores sejam negativos,quando se pensa no emprego do espectro em problemas rela-cionados à comparação de grafos, não é necessariamente verdadeque eles não possam ser aplicados a tais problemas pois, comosabemos, eles são muito úteis nas áreas de visão computacionale reconhecimento de padrões, onde a utilização da representaçãode grafos pode induzir medidas de similaridades dos padrões aserem reconhecidos. Em geral essas medidas são definidas em-piricamente. Por isso, Zhu e Wilson procuram mostrar em seuartigo [84], como o ferramental da Teoria Espectral de Grafospode ser aplicado para determinar mais formalmente tais medi-das. Dado que há diversas matrizes associadas a grafos, dentreelas as de adjacência, Laplaciana e Laplaciana sem sinal, aquiestudadas, seria muito útil uma análise comparativa entre asmesmas, para se tentar determinar quais produzem um númeromenor de pares de grafos coespectrais não isomorfos. Isto é o queveremos a seguir.

Definição 5.2. Se dois grafos G e H são não isomorfos e co-espectrais com respeito a uma matriz M então eles formam umpar coespectral com respeito a M . Seja Gn um conjunto finito degrafos de ordem n, e G∗n um subconjunto em que cada grafo temum par coespectral em Gn − G∗n com respeito a M . De acordo

com [30], a razão|G∗n||Gn|

é chamada de incerteza coespectral de

ordem n com respeito a M .

5.4 Coespectralidade e aplicações 137

n 4 5 6 7 8 9 10 11rn 0 0.059 0.064 0.105 0.139 0.186 0.213 0.211sn 0.182 0.118 0.103 0.098 0.097 0.069 0.053 0.038

Tabela 3 – Incertezas coespectrais de A e Q, G até 11 vértices.

Figura 46 – Índice de incerteza: G coespectrais até 11 vértices.

A incerteza coespectral de ordem n ≤ 11 com respeitoà matriz de adjacência, denotada por rn, e com respeito à ma-triz Laplaciana sem sinal, denotada por sn, determinadas porHaemers e Spence e citadas em [30], estão na Tabela 3. A in-certeza coespectral com respeito à matriz Laplaciana, denotadapor ℓn, será utilizada mais adiante na Tabela 4. De acordo com


Figura 47 – Índice de incerteza de A(G), G até 21 vértices.

[84], esses pesquisadores investigaram a coespectralidade de grafosde até 11 vértices. Segundo eles, a matriz de adjacência parecea pior representação, a matriz Laplaciana é superior e a matrizLaplaciana sem sinal é melhor ainda, em termos de não produzirum grande número de pares coespectrais de grafos. A Laplacianasem sinal contribui com um máximo de 3.8% desses pares, paragrafos de até 11 vértices, conforme a Figura 46 e a Tabela 3.Isso parece uma taxa muito boa, se comparada com as taxas dasoutras matrizes e se considerado o número de vértices dos grafos(ainda pequeno) nas simulações realizadas.

Ainda de acordo com [84], Schwenk mostrou que para

5.4 Coespectralidade e aplicações 139

n suficientemente grande, “quase todas as árvores" são coespec-trais, ou seja, a menos de um número finito delas, as demais con-stituem pares não isomorfos coespectrais. Isto não é muito bom,na medida que desejamos uma representação de grafos com umapequena percentagem de grafos com tais propriedades. Foi entãoque Zhu e Wilson, [84], decidiram estender as simulações feitasanteriormente pelos pesquisadores já citados e investigaram acoespectralidade das árvores de até 21 vértices. Veja as Figuras47 e 48 e a Tabela 4.

Figura 48 – Índice de incerteza de L(G) com G até 21 vértices.

Como as árvores são grafos bipartidos, segundo a Proposição5.4, seus espectros em relação às matrizes Laplaciana e Lapla-


n ♯(T ) rn ℓn = sn A(T )&L(T )8 23 0.087 0 09 47 0.213 0 010 106 0.075 0 011 235 0.255 0.0255 212 551 0.216 0.0109 213 1301 0.319 0.0138 214 3159 0.261 0.0095 1015 7741 0.319 0.0062 216 19320 0.272 0.0035 1417 48629 0.307 0.0045 4018 123867 0.261 0.0019 3819 317955 0.265 0.0014 6420 823065 0.219 0.0008 14821 2144505 0.213 0.0005 134

Tabela 4 – Índices coespectrais para A(T ), L(T ) e A(T )&L(T ).

ciana sem sinal coincidem. Assim, podemos constatar que, nocaso das árvores, a incerteza coespectral associada à matriz Lapla-ciana (e, portanto à Laplaciana sem sinal) é muito menor (próx-imo a zero) que aquela correspondente à matriz de adjacência(em torno de 22%). Embora isto não contrarie o resultado deSchwenk para as árvores, podemos esperar que com relação aospares coespectrais de grafos não isomorfos, mesmo para as ár-vores, a matriz Laplaciana sem sinal é, sem dúvida, uma boaescolha para representação dos grafos. A Tabela 4 discretiza osresultados ilustrados nas Figuras 47 e 48, [84].

Naturalmente que os índices coespectrais rn e ℓn, nas3a e 4a colunas da Tabela 4, correspondem, respectivamente, àsmatrizes A(T ), L(T ) (esta última, dado que T é uma árvore, éigual a Q(T )). Daí, podemos deduzir que a matriz Laplaciana é

claramente superior à de adjacência para as árvores das ordensconsideradas. Além disso, a sequência gerada por esses índicestende a decrescer, sugerindo que eles podem ser desprezíveis paraárvores muito grandes. A tendência da sequência gerada pelosíndices da matriz de adjacência é menos definida, mas parecedecrescer depois de 15 vértices. Os resultados de Zhu e Wilson,[84], parecem confirmar aqueles de Haemers e Spence. A últimacoluna da Tabela 4 mostra o número de pares de árvores quesão ao mesmo tempo coespectrais em relação a A e a L e sendo,cada valor considerado de n, muito pequeno. Como é possívelque as árvores (no caso geral, os grafos) de cada par não se-jam correlacionados entre si, a combinação desses dois espectros(no caso das árvores) e de três ou mais espectros (no caso dosgrafos) poderia ser utilizada nos problemas de comparação e/ourelacionamento de grafos tão necessários para o reconhecimentode padrões.

5.5 Exercícios

1. Quantas arestas tem um grafo G de 50 vértices, sabendo-seque o coeficiente do polinômio característico de sua matrizLaplaciana sem sinal Q é p1 = −1950?

2. Determine o índice q1 da matriz Laplaciana sem sinal deum grafo conexo 4-regular com 15 vértices. A partir de q1,determine o índice λ1 da matriz de adjacência A(G) e oíndice µ1 da matriz Laplaciana L(G).

3. Enumere todas as árvores não isomorfas com n = 8 vér-tices. Verifique se há pares coespectrais em relação a A(T )

e em relação a L(T ). Comprove que as taxas r8 e l8 são asdadas na Tabela 4.

4. Enumere todos os grafos conexos não isomorfos com n = 5

vértices. Verifique se há pares coespectrais em relação aA(G), em relação a L(T ) e em relação a Q(G). Comproveque as taxas r5, s5 e l5 são as dadas na Tabela 3.

5. Seja G um grafo r-regular e Q-integral. Prove que G éQ-integral.


Este capítulo trata da matriz Laplaciana sem sinal, queao contrário das matrizes tratadas nos capítulos anteriores, aindaé pouco (ou quase nada) abordada nos livros de Teoria Algébricae/ou Espectral dos Grafos. No entanto, o interesse pelo seu es-tudo, para descobrir como ela pode determinar propriedades es-truturais dos grafos, vem crescendo muito nos dias atuais. Istose deve às aplicações práticas em Ciência da Computação que,cada vez mais, vêm se utilizando de invariantes decorrentes dessamatriz. Assim, as recomendações que fazemos se limitam a arti-gos.

Segundo Cvetković, Rowlinson & Simić [30], tendo emvista as simulações feitas em [32] e [84], o baixo índice de coespec-tralidade da matriz Laplaciana sem sinal é a principal motivaçãopara o seu recente estudo. D.Cvetković e Simić vêm desenvol-vendo uma Teoria Espectral de Grafos baseada nas propriedadesdesta matriz, [25], [26] e [27]. Temos ainda o texto de Zhu e Wil-son [84], que motiva os pesquisadores em visão computacional e


reconhecimento de padrões a utilizarem todo o vasto ferramen-tal da Teoria Espectral dos Grafos, principalmente os invariantesque poderão decorrer da matriz Laplaciana sem sinal.

145

6 Algoritmos de Localização de

Autovalores

Neste capítulo descrevemos uma metodologia para lo-calizar autovalores de certas matrizes simétricas. Esse método,baseado na diagonalização dessas matrizes e na Lei da Inérciade Sylvester, permite que se determine o número de autovaloresem um dado intervalo. Várias aplicações dessa técnica de locali-zação serão apresentadas. O algoritmo que descrevemos é muitoeficiente qundo aplicado a matrizes associados a algumas classesde grafos, em particular árvores e grafos threshold.

6.1 Motivação

Dada uma classe C de matrizes simétrica reais, gostaría-mos de poder localizar eficientemente os autovaloresde de umamatriz A ∈ C. O propósito deste capítulo é descrever um pro-cedimeto geral que tem sido usado para matrizes de adjacênciasde árvores [55], para matrizes de adjacências de grafos threshold[58], para matrizes Laplacianas de árvores [39, 16], para matrizesdistâncias de grafos threshold [57] e para matrizes Laplacianasnormalizadas de árvores [15]

Lembremos, antes de mais nada, a definição de con-gruência de matrizes.

Definição 6.1. Dizemos que duas matrizes R e S são congru-entes se existe uma matriz não singular P que satisfaz R =

146 Capítulo 6. Algoritmos de Localização de Autovalores

PTSP .

Para nosso propósito, a importância de matrizes congru-entes está no seguinte resultado, chamado de Lei da Inércia deSylvester, cuja prova pode ser encontrada no Apêndice, Teorema7.3.

Teorema 6.1. Duas matrizes reais simétricas de ordem n × n

são congruentes se e somente se elas têm o mesmo número deautovalores negativos e o mesmo número de autovalores posi-tivos.

Agora suponhamos que existe um algoritmo +Diagonalize+que dado como input uma matrix n× n A, e um escalar x ∈ R,+Diagonalize+$(A,x)$ dá como output uma matriz diagonal Dcongruente a Bx = A+xI. Usando a Lei de Sylvester da Inércia,é fácil provar [58, Teo. 3] o seguinte resultado.

Teorema 6.2. Seja D = Diagonalize(A,−x).

1. O número de entradas positivas de D é o número de auto-valores de A maiores que x.

2. O número de entradas negativas de D é o número de au-tovalores de A menores que x.

3. O número de entradas nulas de D é a multiplicidade de x

como autovalor de A.

Assim, segue como consequência imediata o seguinte

Corolário 6.1. Contando multiplicidades, o número de autova-lores de A no intervalo (α, β], é o número de entradas positivasna diagonalização de B−α, menos o número de entradas positivasna diagonalização de B−β.

6.1 Motivação 147

Essa observação mostra que podemos determinar o númerode autovalores de A em um intervalo fazendo duas chamadaspara o algoritmo +Diagonalize+ como mostrado na Figura 49.

Algorithm RootCount(G,α,β)d1← the diagonal computed by Diagonalize+(G,−α)d2← the diagonal computed by Diagonalize+(G,−β)return |{i | d1(i) > 0}| − |{i | d2(i) > 0}|

Figura 49 – Número de autovalores em (α, β].

Se sabemos que o intervalo (α, β] contém pelo menosum autovalor, então podemos localizar o maior autovalor do in-tervalo por um algoritmo do tipo divide-e-conquista como o daFigura 50, que localiza o maior autovalor com uma precisão de-sejada ϵ.

O número de iterações executadas pelo algoritmoLocateRightmost é uma função logarítmica do tamanho do in-tervalo. Assim, se o algoritmo Diagonalize é linear, então, comum intervalo de tamanho k, podemos aproximar um autovalorcom tempo de execução O(n log(k)).

Não queremos aqui discutir as potencialidades numéri-cas de um (ainda hipotético!) algoritmo para localizar autovalo-res. Queremos chamar atenção que tal algoritmo depende fun-damentalmente de um procedimento eficiente de diagonalizaçãode matrizes.

O restante deste capítulo é devotado ao desenvolvimentode tal procedimento. Primeiramente faremos a apresentação paraa classe de matrizes de adjacência de árvores. A seguir faremos odesenvolvimento para grafos threshold. Também desenvolvemos


Algorithm LocateRightmost(G,α,β)do

γ ← (α+ β)/2if RootCount(G,γ,β) > 0

α← γelse

β ← γwhile β − α > ϵreturn γ

Figura 50 – Localizando o maior autovalor.

algumas aplicações dos algoritmos, assim como apontaremos naliteratura outras extensões e/ou aplicações desse procedimento.

6.2 Adjacência de árvores

Seja T uma árvore com n vértices e matriz de adjacênciaA. Consideremos a matriz Bα = A + αI para um escalar α.Vamos desenvolver um algoritmo para diagonalizar a matriz Bα.Mais precisamente, queremos determinar uma matriz diagonal Dque seja congruente a Bα.

Figura 51 – Vértice vk com filho vj e pai vl

6.2 Adjacência de árvores 149

A árvore tem uma raiz que pode ser um vértice arbi-trário, mas a numeração dos vértices v1, . . . , vn deve ser tal quese vi é um filho de vk então k < i. Portanto a raiz é semprev1. Para cada vértice v, armazenamos seu valor diagonal d(v).Inicialmente, d(v) = α, para todo v ∈ V .

Como ilustração, consideremos um vértice vk com filho(s)vj como na Figura 51, cuja porção da matriz Bα é

......

. . . akk . . . 1...

.... . . 1 . . . ajj . . .

...

Se um pai vk tem todos os filhos com elementos não

nulos na diagonal, cada filho pode ser usado para anular seusdois elementos não nulos fora da diagonal. Por exemplo, se ovértice vj , com pai vk tem valor na diagonal d(vj) ̸= 0, então asseguintes operações linha e coluna removem os 1’s nas entradaskj e jk.Rk ← Rk − 1

d(vj)Rj

Ck ← Ck − 1d(vj)

Cj

o que resulta na matriz

......

. . . akk − 1ajj

. . . 0...

.... . . 0 . . . ajj . . .

...


É importante observar que a ordem dos vértices impedeque a matriz adquira entradas não nulas onde antes eram nulas.Assumindo que todos os filhos c do vértice v têm elementos diag-onais não nulos, então, coletivamente, o valor de d(v) é alteradode acordo com

d(v)← d(v)−∑c∈C

1

d(c). (6.2.1)

A dificuldade de diagonalização surge quando algum dosfilhos vj de vk tem d(vj) = 0. Assumimos agora que vi e vj sãofilhos de vk, cujo pai é vl. Um dos filhos (digamos) vj tendod(vj) = 0 é selecionado.

O vértice vj pode ser usado para anular os dois ele-mentos não nulos fora da diagonal de qualquer outro filho vi daseguinte maneira.Ri ← Ri −Rj

Ci ← Ci − Cj

O vértice vj é então usado para anular as duas entradas que re-presentam a aresta entre vk e seu pai vl:Rl ← Rl −Rj

Cl ← Cl − Cj

Estas duas últimas operações de fato desconectam ografo, removendo a aresta entre vk e seu pai vl. Mas isso nãocausa problemas. Neste momento a submatriz com linhas e co-

6.2 Adjacência de árvores 151

lunas i, j, k, l foi transformada da seguinte forma.

l

k

j

i

α 1

1 α 1 1

1 0

1 c

−→

l

k

j

i

α 0

0 α 1 0

1 0

0 c

A seguir, as seguintes operaçõesRk ← Rk − α

2Rj

Ck ← Ck − α2Cj

produzem:

l

k

j

i

α 0

0 0 1 0

1 0

0 c

E finalmente as operaçõesRj ← Rj +Rk

Cj ← Cj + Ck

Rk ← Rk − 12Rj

Ck ← Ck − 12Cj


conduzem à forma diagoanalizada

l

k

j

i

α 0

0 − 12 0 0

0 2

0 c

Os valores 2 e −12 não são particularmente importantes mas sim

o sinal deles. O resultado final é que d(vj) = 2 e d(vk) = −12 .

Se vk não é a raiz da árvore, então a aresta incidente ao seupai é removida. Os outros filhos de vk não são afetados pelasoperações, incluindo outros com valor diagonal zero.

Uma observação extremamente importante é que, em-bora tenhamos usado a matrix para justificar o procedimento, oalgoritmo necessita somente dos valores da diagonal. Assim, serotularmos os vértices com os valores diagonais, ele pode ser exe-cutado diretamente na árvore, procedendo de “baixo para cima”(das folhas para a raiz), de acordo o algoritmo da Figura 52.

As justificativas acima mostram a validade do seguinteteorema.

Teorema 6.3. Para uma árvore T com matriz de adjacências Ae um número real α, o algoritmo Diagonalize determina umamatriz diagonal D que é congruente a A+ αI.

6.3 Aplicações para árvores 153

Input: tree T, scalar αOutput: diagonal matrix D congruent to A(T ) + αI

Algorithm Diagonalize(T, α)initialize d(v) := α, for all vertices vorder vertices bottom up

for k = 1 to nif vk is a leaf then continue

else if d(c) ̸= 0 for all children c of vk then

d(vk) := d(vk)−∑

1d(c), summing over all children of vk

else

select one child vj of vk for which d(vj) = 0d(vk) := −1

2d(vj) := 2if vk has a parent vl, remove the edge vkvl.

end loop

Figura 52 – Diagonalizando A+ αI.

6.3 Aplicações para árvores

Primeiramente vamos ilustrar a aplicação do algoritmoapresentando alguns exemplos.

6.3.1 Exemplo

Exemplo 6.1. Consideremos a árvore mostrada no lado es-querdo da Figura 53. Colocando α = 0, diagonalizamos a matrixde acordo com o algoritmo, obtendo a floresta do lado direitoda figura. Concluimos que a árvore original tem dois autovalo-res positivos e um nulo. O cálculo da Figura 54 mostra que não


02

2−1/2

−1/2

0 0

0 0

0

Figura 53 – Dois autovalores positivos.

−2 −2

−2

−2

−2

−2 −2

−2

−1/2

−1

Figura 54 – Todos os autovalores menores que 2.

há autovalores maiores ou iguais a 2. Na aplicação do algoritmomostrado na Figura 55, vemos que um autovalor positivo é maiorque 1 e na Figura 56 podemos ver que dois são maiores que 1

2 .Podemos concluir que um autovalor positivo está em ( 12 , 1) e umestá em (1, 2). Pode-se mostrar que os autovalores da árvore são0, ±

√2±√2.

Vamos agora fazer uma aplicação típica do algoritmo,ilustrando como uma análise qualitativa permite a obtenção deresultados não sobre um grafo em particular, mas sobre umaclasses de grafos.

6.3 Aplicações para árvores 155

−1 −1

−1

−1−1

−1 −1

−11

−1

Figura 55 – Um autovalor maior que 1.

−1/2 −1/2

−1/2 −1/2

−1/2

7/2

−1/2 −1/2

−1/2

17/14

Figura 56 – Dois autovalores maiores que 12 .

6.3.2 Centopeias

Definição 6.2. Uma centopeia é uma árvore cuja remoção dasfolhas a transforma em um caminho.

As folhas (pendentes) de uma centopeia são chamadasde pernas e os vértices não pendentes de nós dorsais. Em geral,uma centopeia pode ser definida com como T (b, k) onde b ∈ Né o número de nós dorsais e k = (k1, . . . , kb) ∈ Nb denota aquantidade de pernas para cada nó dorsal.

Teorema 6.4. [55] Em uma centopeia, qualquer autovalor não


nulo é simples. Além disso, uma centopeia com b nós dorsaistem b autovalores positivos e b negativos.

Demonstração: Vamos assumir que a raiz é o nó dorsal mais àdireita e vamos diagonalizar da esquerda para a direita.

Seja λ um autovalor não nulo de uma centopeia. Sabe-mos que pelo menos um valor 0 deve aparecer na diagonal. Comoinicialmente é atribuído λ ̸= 0 às pernas e isso nunca muda, ovalor zero deve aparecer em um nó dorsal. Se um zero aparece emum nó dorsal, o algoritmo muda para 2, a menos que isso ocorrana raiz (último estágio) e, nesse caso, isso fica inalterado. Assimsomente um zero ocorre na diagonal e pelo Teorema 6.2(iii), λ ésimples. Para provar o segundo enunciado, seja α = 0, e observe-mos que o algoritmo produzirá exatamente b valores positivos eb valores negativos. Isso está ilustrado na Figura 57.

0 0 0

0

0 0

0

0

0

0 0

0

0 0 002 2 2 2

−1/2 −1/2 −1/2 −1/2

Figura 57 – Centopeia diagonalizada com α = 0

Corolário 6.2. Seja C uma centopeia com b nós dorsais e graumáximo ∆. Se b > 2

√∆− 1 então C tem um autovalor não

inteiro.

6.4 Adjacências de grafos threshold 157

Demonstração: Pelo Teorema 6.4, C tem b autovalores positivose distintos. É sabido [61, Proposition 3.1 (iii)] que eles são limita-dos por 2

√∆− 1. Como existem exatamente ⌊2

√∆− 1⌋ inteiros

positivos nesse intervalo e b > ⌊2√∆− 1⌋, pelo princípo da casa

dos pombos, pelo menos um autovalor deve ser não inteiro.

6.4 Adjacências de grafos threshold

Nesta seção apresentaremos um algoritmo de ordem O(n)

para construir uma matrix diagonal congruente a A + xI, paraqualquer numero real x, onde A é matriz de adjacências de umgrafo threshold.

Cabe ressaltar que, diferentemente de árvores, que têmpoucas arestas e portanto suas matrizes de adjacências são es-parsas, os grafos threshold podem ter muitas arestas, implicandomatrizes densas. Note-se que a quantidade de entradas (não) nu-las de uma matriz é considerada uma medida da dificuldade dese operar com ela. Quanto mais entradas não nulas, maior é a di-ficuldade. Nesse sentido, determinar um algoritmo eficiente (comtempo de execução de O(n)) para matrizes de grafos threshold éum desafio maior. Por outro lado, isso se torna possível porqueexploramos de forma eficiente a estrutura bastante particularque esta classe de grafos apresenta, como veremos a seguir.

Os grafos threshold foram introduzidos por Chvátal eHammer [20] nos anos 70. Eles são uma importante classe degrafos devido às várias aplicações em psicologia, sicronização deprocessos paralelos e outros [65]. Provavelmente por esta razão,eles aparecem na literatura com vários nomes equivalentes.


Existem muitas formas de definir os grafos threshold,mas para nosso propósito usaremos a caracterização através deuma sequência binária, que é um processo recursivo que iniciacom um vértice isolado e que, a cada passo, ou um novo vérticeisolado é adicionado ou um vértice adjacente a todos os vérticesanteriores é adicionado (vértice dominante). Assim, para definir-mos um grafo threshold G com n vértices, podemos consideraruma sequência de tamanho n composta por caracteres 0 e 1. De-notaremos por 0 sempre como o primeiro caracter da sequência;ele representa o primeiro vértice do grafo. A seguir cada 0 repre-senta a adição de um vértice isolado e 1, a adição de um vérticedominante. O número de caracteres 1 na sequência, é chamadode traço do grafo, indica o número de vértices dominantes.

Definição 6.3. Um grafo threshold G = (V,E) de ordem n édefinido por uma sequência binária (b1, b2, . . . , bn), onde bi = 0,representa adição de um vértice isolado e bi = 1, representaadição de um vértice dominante.

Exemplo 6.2. A Figura 6.4, mostra a construção de um grafothreshold G = (V,E) que começa com 3 vértices isolados, seguidode 1 vértice dominante, 4 vértices isolados e 1 vértice final do-minante. A sequência binária que representa o grafo threshold G

é (0, 0, 0, 1, 0, 0, 0, 0, 1) e seu traço é igual a 2.

Podemos construir a matriz de adjacências A de umgrafo threshold G através da sequência binária associada a G,

fazendo a enumeração dos vértices a mesma da sequência binária.Por exemplo a matriz de adjacência do grafo threshold G repre-


Figura 58 – Construção de um grafo threshold

sentado por (0, 0, 0, 1, 1, 1, 0, 0, 1) é

0 0 0 1 1 1 0 0 1

0 0 0 1 1 1 0 0 1

0 0 0 1 1 1 0 0 1

1 1 1 0 1 1 0 0 1

1 1 1 1 0 1 0 0 1

1 1 1 1 1 0 0 0 1

0 0 0 0 0 0 0 0 1

0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 0

Seja G um grafo threshold com sequência binária (b1, . . . , bn),

e seja A = [aij ] sua matriz de adjacência. É fácil ver que se bi = 1,

as entradas aij = aji = 1, para i < j. E se bi = 0, aij = aji = 0,

para i < j.

6.4.1 Diagonalizando A+ xI

O algoritmo de diagonalização para grafos threshold G

constrói uma matriz diagonal D congruente a A+xI, onde A é a


matriz de adjacência de um grafo threshold G e x é um númeroreal.

Assumimos que A é de ordem n, o algoritmo executan−1 passos e funciona na matriz de baixo para cima e da direitapara esquerda. Em cada passo, as linhas e colunas m e m −1 participam nas operações linha e coluna. A diagonalização éobtida pelo fato que no fim de cada passo, todas as entradasda linha e coluna m serão nulas com exceção do elemento dadiagonal.

Após n−m passos do algoritmo, a matriz parcialmentediagonalizada é da forma exibida na figura 3.2. O objetivo dopasso seguinte é remover os v′s da linha e coluna m. Note quese v = 0, não precisamos fazer nada.

u v 0 · · · 0...

...u v

u . . . u x v...

...v . . . v v α 0 0

0 0 δm+1 · · · 0...

.... . .

...0 0 · · · 0 δn

.

O nosso algoritmo constrói uma matriz diagonal D con-gruente a Bx = A+ xI, onde A é a matriz de adjacência de umgrafo threshold G, e x é um número real. Mais precisamente, acada passo, nosso procedimento sempre que executa uma oper-ação elementar na k-ésima linha, executa a mesma operação nak-ésima coluna, o que garante que a matriz resultante é congru-ente à matriz original.


Dessa forma, precisamos focar somente na submatrizrestante m×m. Consideremos a sequência binária de G dada por(b1, b2, . . . , bn). Nosso algoritmo considera três casos principais.

Caso 1: bm−1 = bm = 1. Então a submatriz tem a seguinteforma:

m− 1

m

1 1...

...1 1

1 . . . 1 x 1

1 . . . 1 1 α

Fazendo as operações nas linhas e colunaslm ← lm − lm−1

Cm ← Cm − Cm−1,a maior parte dos elementos não nulos da linha e coluna m foramremovidos, conforme a matriz abaixo ilustra. Agora devemos re-mover as duas entradas iguais 1−x. Assim existem três subcasos,dependendo se α+ x− 2 ̸= 0 e se x = 1.

m− 1

m

1 0...

...1 0

1 . . . 1 x 1− x

0 . . . 0 1− x α+ x− 2

Subcaso 1a: α + x − 2 ̸= 0. Então podemos proceder com as

seguintes operações:


lm−1 ← lm−1 − 1−xα+x−2 lm

Cm−1 ← Cm−1 − 1−xα+x−2Cm,

obtendo

m− 1

m

1 0...

...1 0

1 . . . 1 γ 0

0 . . . 0 0 α+ x− 2

onde γ = x− (1−x)2

α+x−2 = αx−1α+x−2 .

Subcaso 1b: Se α + x = 2 e x = 1, então a submatriz é daforma:

1 0...

...1 0

1 . . . 1 1 0

0 . . . 0 0 0

ou seja, já está na forma desejada.

Subcaso 1c: Se α + x − 2 = 0 e x ̸= 1, então a matriz é daforma

1 0...

...1 0

1 . . . 1 x 1− x

0 . . . 0 1− x 0


Como 1− x ̸= 0, para cada i, 1 ≤ i ≤ m− 2 fazemosli ← li − 1

1−x lm

Ci ← Ci − 11−xCm.

Isso anula os 1′s na coluna m− 1 e linha m− 1 :

0 0...

...0 0

0 . . . 0 x 1− x

0 . . . 0 1− x 0

Fazendo as seguintes operaçõeslm−1 ← lm−1 +

12 lm

Cm−1 ← Cm−1 +12Cm,

substituimos a diagonal x por 1, assim basta tomarlm ← lm − (1− x)lm−1

Cm ← Cm − (1− x)Cm−1

para obtermos finalmente a matriz diagonalizada

0 0...

...0 0

0 . . . 0 1 0

0 . . . 0 0 −(1− x)2

A diferença desse subcaso é que as entradas da linha e colunam − 1 também foram anuladas. Vamos memorizar isso fazendo


a seguinte atribuição.bm−1 ← 0.

Caso 2: bm−1 = 0 e bm = 1. Então a submatriz tem a seguinteforma:

0 1...

...0 1

0 . . . 0 x 1

1 . . . 1 1 α

Após trocarmos as linhas m e m− 1 e as colunas m e m− 1, amatriz toma a seguinte forma.

1 0...

...1 0

1 . . . 1 α 1

0 . . . 0 1 x

Existem apenas dois subcasos, dependendo se x é zero ou não.

Subcaso 2a: Se x = 0. Então para cada i, 1 ≤ i ≤ m−2 façamosas operaçõesli ← li − lm

Ci ← Ci − Cm

para anular os 1′s da linha e coluna m − 1, a esquerda e acimade α. Com as operaçõeslm−1 ← lm−1 +

1−α2 lm

Cm−1 ← Cm−1 +1−α2 Cm


lm ← lm − lm−1

Cm ← Cm − Cm−1

obtemos a matriz da forma

0 0...

...0 0

0 . . . 0 1 0

0 . . . 0 0 −1

Subcaso 2b: Se x ̸= 0. Então fazemos as operaçõeslm−1 ← lm−1 +

1x lm

Cm−1 ← Cm−1 +1xCm

obtendo a matriz da forma:

1 0...

...1 0

1 . . . 1 α− 1x 0

0 . . . 0 0 x

Como a linha e coluna m−1 foram preenchidas por 1′s, devemosfazer a seguinte atribuição

bm−1 ← 1.

Caso 3: bm = 0. Não é preciso fazer qualquer operação já que asubmatriz é da forma


0...

...0

. . . x 0

0 . . . 0 0 α

O algoritmo de diagonalização baseado nestas operaçõesestá mostrado na Figura 59. Notemos que a única informação im-portante é a descrição do grafo e os valores da diagonal, entãoele pode assim ser implementado com dois vetores de compri-mento n. Assumimos que G é representado por (b1, b2, . . . , bn)

e o vetor d = (d1, d2, . . . , dn) representa os valores da diagonalda matrix resultante da aplicação do algoritmo, que inicialmenteé inicializado com x em todas as suas posições. Para enfatizar,observamos que quando bm = 0, como no caso 3, o algoritmonão é executado e move-se para o próximo passo.

Teorema 6.5. Dados G e x, onde G é um grafo threshold coma matriz de adjacência A, o algoritmo de diagonalização calculauma matriz diagonal D congruente a A+ xI.

6.4.2 Exemplos

Ilustraremos o algoritmo com três exemplos. O primeiroexemplo assumimos que G é um threshold representado por(0, 1, 1, 1), e x = 0. Após inicializarmos, existirão três passos,m = 4, 3, 2.

Para m = 4, já que b3 = b4 = 1 e α = x = 0, o primeiropasso o algoritmo executa o subcaso 1a, e as seguintes atribuições


Algorithm Diagonalize(G, x)initialize di ← x, for all ifor m = n to 2

α← dmif bm−1 = 1 and bm = 1

if α+ x ̸= 2 //subcase 1a+

dm−1 ← αx−1α+x−2

dm ← α+ x− 2else if x = 1 //subcase 1b+

dm−1 ← 1dm ← 0

else //subcase 1c+

dm−1 ← 1dm ← −(1− x)2

bm−1 ← 0else if bm−1 = 0 and bm = 1

if x = 0 //subcase 2a+

dm−1 ← 1dm ← −1

else //subcase 2b+

dm−1 ← α− 1x

dm ← xbm−1 ← 1

end loop

Figura 59 – Diagonalizing A(G) + xI.

são feitas:

d3 ←αx− 1

α+ x− 2=

1

2

d4 ← α+ x− 2 = −2

Para m = 3, o segundo passo do algoritmo tambémexecuta o subcaso 1a, desde que b2 = b3 = 1, e x = 0, α = 1

2 ,


logo

d2 ←αx− 1

α+ x− 2=

2

3

d3 ← α+ x− 2 = −3

2

Para m = 2, o passo final do algoritmo é executado osubcaso 2a, desde que b1 = 0, b2 = 1, e x = 0, logo

d1 ← 1

d2 ← −1

A seguinte tabela fornece os passos do algoritmo em cada estágio:

bi di

0 0

1 0

1 0

1 0

inicial

bi di

0 0

1 0

1 12

1 −2após 1a

bi di

0 0

1 23

1 −32

1 −2após 1a

bi di

0 1

1 −1

1 −32

1 −2após 2a

Nosso segundo exemplo, assumimos que G é representado por(0, 1, 0, 1) e x =

√3+12 . Esse exemplo ilustra como o subcaso 1c

pode aparecer. Ele também mostra que o caso 3 pode ocorrer,mesmo sem vértices isolados.

Após inicializarmos, o primeiro passo será o subcaso 2b,já que b3 = 0, b4 = 1 e α = x ̸= 0. Note que 1

x =√3− 1. Assim

as atribuições serão:

d3 ← x− 1

x=

3−√3

2


d4 ← x =

√3 + 1

2

b3 ← 1

Como b3 torna-se 1, o próximo passo é o caso 1, já que b2 = 1 eb3 = 1. Entretanto, desde que d3 + x = 2 e x ̸= 1, o subcaso 1cserá executado:

d2 ← 1

d3 ← −(1− x)2 =

√3− 2

2

b2 ← 0

Finalmente, já que b2 torna-se zero, o passo final é o caso 3e assim não é necessário alguma operação. A seguinte tabelafornece os passos do algoritmo em cada estágio:

bi di

0√3+12

1√3+12

0√3+12

1√3+12

inicial

bi di

0√3+12

1√3+12

1 3−√3

2

1√3+12

após 2b

bi di

0√3+12

0 1

1√3−22

1√3+12

após 1c

bi di

0√3+12

0 1

1√3−22

1√3+12

após 3

O próximo exemplo faz uma aplicação do Teorema 6.2para localizar os autovalores.

Exemplo 6.3. Considere o grafo threshold G = (0, 0, 0, 1, 1).

Para x = 0, o algoritmo de diagonalização fornece os seguintes


valores d = (0, 0, 1,−1,−2). De acordo com o Teorema 6.2, sig-nifica que x = 0 é um autovalor com multiplicidade 2, e queexiste um autovalor de G maior do que 0. Quando aplicarmoso algoritmo ao mesmo grafo para x = −4, obtemos a diagonalcom os valores d = (−3

4 ,−4,−4,−4,−10). Isso implica que todosos autovalores de G são menores do que 4. Finalmente podemosconcluir que existe um único autovalor no intervalo (0, 4].

6.4.3 Simplicidade dos autovalores

Faremos nesta seção uma aplicação do algoritmo de di-agonalização. Vamos mostrar que todo autovalor de um grafothreshold G,λ ̸= 0,−1 é um autovalor simples.

Lembremos que um autovalor λ de um grafo G é sim-ples se λ tem multiplicidade igual a 1 como raiz do polinômiocaracterístico. Seja G um grafo threshold, segue do algoritmo dediagonalização o seguinte resultado sobre os autovalores princi-pais de G.

Teorema 6.6. Em grafos threshold, a multiplicidade de um au-tovalor λ é um, a menos que λ = 0 ou λ = −1.

Demonstração: Assumimos que λ é um autovalor. Então o al-goritmo de diagonalização de (G,−λ) produz pelo menos umzero na diagonal. Existem três maneiras de um zero aparecer nadiagonal:(1) quando inicializamos;(2) quando atribuimos dm ← 0 para algum m ≥ 2;

(3) quando atribuimos dm−1 ← 0 para m = 2;

Um zero pode ser produzido quando inicializamos o algoritmo so-

6.5 Exercícios 171

mente quando λ = 0. Se a atribuição dm ← 0 ocorre, para algumm ≥ 2, uma verificação cuidadosa do algoritmo, mostra que eladeverá ocorrer no subcaso 1b. Assim a diagonal inicializada comx = 1, implica que λ = −1. Suponha agora que λ ̸= 0,−1, e umzero tem sido produzido no passo final pela atribuição dm−1 ← 0

para m = 2. Logo somente um zero pode aparecer na diagonal, esua multiplicidade é um. �

Assim, temos que os autovalores diferentes de 1 e 0 deum grafo threshold G são simples.

6.5 Exercícios

1. Considere a estrela K1,n.

a) Prove que√n é autovalor da estrela.

b) Verifique que 0 é autovalor da estrela com multiplici-dade n− 1.

c) Conclua que K1,n é integral se, e somente se, n é umquadrado perfeito.

2. Considere a árvore T formada por P3 com b vértices adja-centes a cada extremidade:

a) Verifique que√b e√b+ 2 são autovalores de T .

b) Calcule a multiplicidade do autovalor 0 e conclua queT tem exatamente 5 autovalores distintos.

3. Calcule a multiplicidade de −1 como autovalor do grafothreshold G = (0, 0, 0, 0, 1, 1) do exemplo 6.3. Encontre aquantidade de autovalores distintos de G.


4. Verifique que o índice do grafo threshold G = (0, 0, 0, 0, 1, 1)

do exemplo 6.3 está em (2, 4].

6.5.1 Notas Bibliográficas

O algoritmo apresentado para matrizes de adjacênciasde árvores foi adaptado para funcionar com matrizes Laplacianas[39]. Aplicações dessa versão do algoritmo incluem o ordena-mento de árvores pela energia Laplaciana [40] e a distribuiçãode autovalores Laplacianos de árvores [16, 54].

Também foi adaptado para a matriz Laplaciana normal-izada [15]. Como aplicação específica, nesse mesmo artigo foramcaracterizadas todas as árvores que tem menos do que seis au-tovalores Laplacianos distintos.

O algoritmo para grafos threshold foi estendido paramatrizes distância [57]. Também foram feitas extensões dos al-goritmos para o cálculo do polinômio característico [56].

173

Referências

[1] N.M.M. Abreu, Old and new results on algebraic connec-tivity of graphs, Linear Algebra Appl. 423 (2007), 53-73.

[2] N.M.M. Abreu, R. Del-Vecchio, C. Vinagre, D. Stevanović,“Introdução à Teoria Espectral de Grafos com Aplicações”,Notas em Matemática Aplicada, 27, 2a edição, SBMAC,2012, disponível em , último acesso em 20/01/2014.

[3] N.M.M Abreu, C. M. Justel, O. Rojo e V. Trevisan, Or-dering trees and graphs with few cycles by algebraic con-nectivity, a aparecer em Linear Algebra Appl., 2014.

[4] N.M.M. Abreu e C.S. Oliveira e L.S. de Lima, Con-jecturas geradas automaticamente pelo sistema Auto-GraphiX: provas de algumas desigualdades para o índice damatriz Laplaciana sem sinal, em “Anais do XXXIX SBPO”,Fortaleza, 2007.

[5] R. Balakrishnan, The energy of a graph, Linear AlgebraAppl., 387, 287-295(2004).

[6] S. Barnett, “Matrices Methods and Applications”, OxfordUniversity Press, New York, 1990.

[7] J-C. Bermond, C. Delorme e J.J. Quisquater, Tableof large (△, D)-graphs, Discrete Applied Mathematics,37/38 (1992), 575-577.

174

[8] L.W. Beineke e R.J. Wilson “Topics in Algebraic GraphTheory”, Encyclopedia of Math. Appl., 102, Cambridge,2004.

[9] D. C. Bell, J. S.Atkison, J. W.Carlson, Centrality for dis-ease transmission networks, Social Networks, 21(1999), 1-21.

[10] N. Biggs, “Algebraic Graph Theory”, Great Britain, Cam-bridge University Press, 2a. ed., 1993.

[11] P.O. Boaventura Netto, “Teoria, Modelos e Algoritmos emGrafos”, E. Blücher, 4a edição, 2006.

[12] B. Bollobás, “Graph Theory: An Introductory Course”,Springer-Verlag, 1979.

[13] P. Bonacich, Power and Centrality: A Family of Measures,The American Journal of Sociology, 92(1987), 5, 1170-1182.

[14] S. P. Borgatti, Centrality and network flow, Social Net-works, 27(1)(2005), 55-71.

[15] R. Braga, R. Del-Vecchio, V. Rodrigues e V. Trevisan,Characterizing trees with 4 or 5 disticnt normalizaedLaplacian eigenvalues, Submitted (2014).

[16] R. Braga, V. Rodrigues and V. Trevisan, On the dis-tribuition of Laplacian eigenvalues of trees, Discrete Math-ematics, 313 (2013), 2382-2389.

[17] P.J. Cameron, J.M. Goethals, J.J. Seidel e E.E. Shult, LineGraphs, roots systems, and elliptic geometry, J. Algebra43 (1976), 305-327.

Bibliografia 175

[18] G. Caporossi e P. Hansen, Variable neighborhood searchfor extremal graphs. I. The AutoGraphiX system. DiscreteMathematics, 212 (2000), 29-44.

[19] F.R.K. Chung, “Spectral Graph Theory”, CBMS, Confer-ence Board of the Mathematical Sciences, Regional Con-ference Series in Mathematics, 92, AMS, 1994.

[20] V. Chvátal, P. L. Hammer, Aggregation of inequalities ininteger programming, in Studies in Integer Programming,Annals of Discrete Math., 1, 145–162, North-Holland, Am-sterdam, 1977.

[21] Collatz e Sinogowitz, Spectren endlicher grafen, Abh.Math. Sem., Univer. Hamburg, 21 (1957), 63-77.

[22] D. Cvetković, Graphs and their spectra, Publ. Elektrotehn,Fak., Ser. Mat. Fiz., Univ. Beograd, 354(1971), 1-50.

[23] D. Cvetković, M. Doob e H. Sachs “Spectra of Graphs -Theory and Application”, Pure and Applied Mathematics,Academic Press, New York, 1980.

[24] D. Cvetković, M. Doob e H. Sachs, “Spectra of Graphs,Theory and Application”, 3a edição, Johann AmbrosiusBarth Verlag, Heidelberg-Leipzig, 1995.

[25] D. Cvetković, S.K. Simić, Towards a spectral theory ofgraphs based on the signless Laplacian, I, Publ. Inst.Math.(Beograd) 85 (99) (2009), 19-33.

[26] D. Cvetković, S.K. Simić, Towards a spectral theory ofgraphs based on the signless Laplacian, II, Linear AlgebraAppl. 432(2010), 2257-2272.

176

[27] D. Cvetković, S.K. Simić, Towards a spectral theory ofgraphs based on the signless Laplacian, III, Appl. Anal.Discrete Math. 4 (2010), 156-166.

[28] D. Cvetković, P. Rowlinson e S. Simić, “Eigenspaces ofgraphs”, Encyclopedia of Math. Appl., 66, Cambridge,1997.

[29] D. Cvetković, P. Rowlinson e S. Simić, “Spectra General-izations of Line Graphs: On graphs with least eigenvalue−2”, LMS, Lecture Note Series, 314, Cambridge Univer-sity Press, 2004.

[30] D. Cvetković, P. Rowlinson e S. Simić, Signless Laplacianof finite graphs, Linear Algebra Appl., 423 (2007), 155-171.

[31] D. Cvetković, P. Rowlinson e K.Simić, An Introduction tothe Theory of Graph Spectra, Cambridge University Press,Cambridge, 2009.

[32] E. R. van Dam e W. Haemers, Which graphs aredetermined by their spectrum?, Linear Algebra Appl.,373(2003), 241-272.

[33] M. de Freitas, N. Abreu, R. Del-Vecchio, S. Jurkiewicz,Infinite families of Q-integral graphs, Linear Algebra Appl.,432(2010), 2352-2360

[34] R. Diestel, “Graph Theory”, Graduate Texts in Mathemat-ics, Springer, 173(1997).

[35] J. Donadelli, “Métodos da Álgebra Linear em Teoria deGrafos”, Relatório Técnico 002, Departamento de Infor-mática, UFPR, 2007.

Bibliografia 177

[36] M. Fiedler, Algebraic Connectivity of Graphs, Czechoslo-vak Math. J., 23(1973), 298-305.

[37] L. C. Freeman, A Set of Measures of Centrality Based onBetweenness, Sociometry, 40(1)(1977), 35-41.

[38] L. C. Freeman, Centrality in Social Networks: ConceptualClarification, Social Networks, 1(1979), 215-239.

[39] E. Fritscher, C. Hoppen, I. Rocha, V. Trevisan, On thesum of the Laplacian eigenvalues of a tree, Linear AlgebraAppl. 435 (2011), 371-399.

[40] E. Fritscher, C. Hoppen, I. Rocha, V. Trevisan, Charac-terizing trees with large Laplacian energy, Linear AlgebraAppl. 442 (2014), 20-49.

[41] C. Godsil e G. Royle, “Algebraic Graph Theory”, GraduateTexts in Mathematics, Springer-Verlag, 2001.

[42] J.A.M. Gonçalves, L.S. Portugal, , P. O. Boaventura Netto,As potencialidades de indicadores de centralidade no es-tudo de um corredor ferroviário, em “Anais do XIX AN-PET - Congresso De Pesquisa E Ensino Em Transportes”,Recife, PE, 2005.

[43] R. Grone e R. Merris, Ordering trees by algebraic connec-tivity, Graphs and Combinatorics, 6(1990), 229-237.

[44] R. Grone, R. Merris, The Laplacian spectrum of a graph,SIAM J. Matrix Anal. Appl., v. 11,n. 2 (1990), 218-238.

[45] I. Gutman, The energy of a graph, Ber. Math. Statist.Sekt. Forschungszenturm Graz., 103(1978), 1-22.

178

[46] I. Gutman, D. Vidović e D. Stevanović, Chemical applica-tions of the Laplacian spectrum. VI. On the largest Lapla-cian eigenvalue of alkanes, J. Serb. Chem. Soc., 67(2002),407-413.

[47] I. Gutman, Topology and stability of conjugated hydrocar-bons. The dependence of total π-electron energy on molec-ular topology, J. Serb. Chem. Soc., 70(3)(2005), 441-456.

[48] I. Gutman e B. Zhou, Laplacian energy of a graph, LinearAlgebra Appl., 414 (2006), 29-37.

[49] W. H. Haemers, Interlacing eigenvalues and graphs, LinearAlgebra Appl.. 226–228 (1995) 593–616.

[50] F. Harary, “Graph Theory” , Addison Wesley, 1969.

[51] F. Harary e A.J. Schwenk, Which graphs have integralspectra?, em Bari, R., Harary, F.(Eds), “Graphs and Com-binatorics”, Springer, Berlim, 1974, p. 45-51.

[52] A.R. Horn e Johnson, C.R. “Matrix Analysis”, CambridgeUniversity Press, Cambridge, 1985.

[53] E. Hückel, Quantentheoretische Beitrage Zum Benzolprob-lem, Z. Phys., 70(1931), 204-286,.

[54] D. P. Jacobs e V. Trevisan, A note on Laplacian eigenval-ues in trees, submitted.

[55] D. P. Jacobs e V. Trevisan, Locating the eigenvalues oftrees, Linear Algebra Appl. 434 (2011), 81–88.

[56] D. P. Jacobs, V. Trevisan e F. Tura, Computing the char-acteritic polynomial of threshold graphs, Submitted (2014).

Bibliografia 179

[57] D. P. Jacobs, V. Trevisan e F. Tura, Eigenvalue locationin certain graphs, Submitted (2014).

[58] D. P. Jacobs, V. Trevisan e F. Tura, Eigenvalue location inthreshold graphs, Linear Algebra Appl. 439 (2013), 2762-2773.

[59] http://www.monod.biomath.nyu.edu/tutorials/spectral-analysis.html (em 12/03/2004).

[60] S. Kirkland, J. Molitierno, M. Neumann e B. Sharder, Ongraphs with equal algebraic connectivity, Linear AlgebraAppl., 341(2002), 45-56.

[61] M. Krivelevich, B. Sudakov, The largest eigenvalue ofsparse random graphs, Combinatorics, Probability andComputing, 12 (2003) 61-72.

[62] K.Y. Lin, An elementary proof of the Perron-FrobeniusTheorem for non-negative symmetric matrices, ChineseJournal of Physics, 15(1977), p.283–285.

[63] H.C. Longuest-Higgins, Resonance structures and MO inunsaturated hydrocarbons, J. Chem. Phys. 18(1950), 265-274.

[64] B. Luo, R.C. Wilson e E.R. Hancock, The Independentand Principal Component of Graph Spectra, in “16th In-ternational Conference on Pattern Recognition” (ICPR’02)(2002).

[65] N. V. R. Mahadev, U. N. Peled, “Threshold graphs andrelated topics”, Elsevier, 1995.

180

[66] L. Markenzon, O. Vernet, “Representações Computa-cionais de Grafos”, Notas em Matemática Aplicada, 25,SBMAC, 2006.

[67] B.D. Mckay, On the spectral characterization of trees, ArsCombinatoria III, 1977, 219-232.

[68] B.J. McClelland, Properties of the latent roots of a ma-trix: the estimation of π-eletron energies, J. Chem. Phys.,54(1971), 640-643.

[69] C. D. Meyer, “Matrix Analysis and AppliedLinear Algebra”, SIAM, 2000, disponível emhttp://matrixanalysis.com/, acessado pela última vezem fevereiro de 2014

[70] B. Mohar, The Laplacian Spectrum of Graphs, Graph The-ory, Combinatorics, and Applications, 2(1991), 871-898.

[71] B. Mohar, Eigenvalues, Diameter, and Mean Distance inGraphs, Graphs and Combinatorics, 7(1991), 53-64.

[72] B. Mohar, A novel definition of the Wiener index of trees,J. Chem. Inf. Comp. Sci., 33(1993), 153-154.

[73] D. Poole, “Álgebra Linear”, Cengage Learning Editores,2004.

[74] G. Sabidussi, The centrality index of a graph, Psychome-trika, 31(1966), 581-603.

[75] S. Simić, Z. Stanić, Q-integral graphs with edge-degrees atmost five, Discrete Math., v. 308, pp. 4625-4634, 2008.

Bibliografia 181

[76] Z. Stanić, There are exactly 172 connected Q-integralgraphs up to 10 vertices, Novi Sad J. Math., v. 37, n. 2,pp. 193-205, 2007.

[77] D. Stevanović, I. Stanković, Remarks on hyperenergeticcirculant graphs, Linear Algebra Appl., 400(2005), 345-348.

[78] D. Stevanović, NewGraph system,http://www.sgt.pep.ufrj.br/index.php (em 24/09/2011).

[79] J.L. Szwarcfiter, “Grafos e Modelos Computacionais”, Ed-itora Campus, 1984.

[80] J.L. Szwarcfiter e L. Markenzon, “Estrutura de Dados eseus Algoritmos”, 2a. edição, LTC, Livros Técnicos e Cien-tíficos, 1994.

[81] Wikipedia, http://pt.wikipedia.org/wik, acessado por úl-timo em 22/04/2007.

[82] yEd Graph Editor disponível emhttp://www.yworks.com/en/products_yed_about.htmlacessado por último em 03/10/2013.

[83] B. Zhou, More on energy and Laplacian energy, MATCHCommun. Math. Comput. Chem., 64(2010), 75-84.

[84] P. Zhu, R.C. Wilson, A Study of Graph Spectra for Com-paring Graphs, Relatório Técnico, Universidade de York,UK, 2005.

183

7 Apêndice

Na primeira seção deste Apêndice, provamos o resultadode Teoria de Matrizes utilizado na demonstração da Proposição5.1. Na sequência, apresentamos e provamos cinco resultados im-portantes sobre matrizes simétricas utilizados no decorrer desteestudo da Teoria Espectral de Grafos, no intuito de tornar otexto autossuficiente.

Na escolha do conteúdo para este Apêndice, preferimosenfocar naqueles resultados que não fazem parte dos programasdas primeiras disciplinas de Álgebra Linear, mesmo nos curricu-los de cursos de Matemática. Os resultados que julgamos con-hecidos, serão mencionados apenas para referência. Quando pos-sível, fazemos a passagem da linguagem de matrizes e ÁlgebraLinear para o contexto da Teoria Espectral de Grafos em que oteorema será usado, mas resultados gerais da Teoria de Matrizessão apresentados em suas formulações mais abrangentes. Nestesentido, seguimos a abordagem de [31].

7.1 Um resultado de Teoria de Matrizes

Como referência para esta seção, indicamos [69]. Emprimeiro lugar, apresentamos a regra para cálculo de determi-nantes de matrizes de blocos que utilizaremos adiante:

184 Apêndice

Lema 7.1. Se A e D são matrizes quadradas então

det

[A B

C D

]=

{det(A) det(D − CA−1B), se A−1 existe edet(D) det(A−BD−1C), se D−1 existe.

Demonstração: Se A−1 existe, pode-se escrever[A B

C D

]=

[I O

CA−1 I

][A B

O D − CA−1B

].

Como as matrizes envolvidas são quadradas, da teoria de deter-minantes vem que

det

[I O

CA−1 I

]= det

[I CA−1

O I

]= det(I2) = 1 e

det

[A B

O D − CA−1B

]= det(A) det(D − CA−1B).

Portanto, neste caso,

det

[A B

C D

]= det(A) det(D − CA−1B).

O outro caso é análogo.

Lema 7.2. Sejam B uma matriz m×n e C uma matriz n×m,ambas com entradas em R. Então, para todo λ ∈ R,

λm det(λIn − CB) = λn det(λIm −BC) .

Demonstração: Suponhamos λ ̸= 0 (o caso λ = 0 é trivial). Namatriz

E =

[λIm λB

λIn

],

7.1 Um resultado de Teoria de Matrizes 185

os blocos λIm e λIn são matrizes quadradas e invertíveis. Logo,pelo Lema 7.1, temos

det(E) = det(λIm) det(λIn−C(λIm)−1B) = λm+1 det(In−CB).

Mas também,

det(E) = det(λIn) det(λIm−B(λIn)−1C) = λn+1 det(Im−BC).

Tem-se portanto a igualdade desejada.

Proposição 7.1. Sejam A uma matriz m× n e B uma matrizn×m. Então:

(i) se m = n então AB e BA possuem o mesmo polinômiocaracterístico;

(ii) se m ̸= n, os polinômios característicos de AB e BA sãodiferentes, mas as matrizes possuem os mesmos autovalo-res não nulos.

Demonstração: (i) Se m = n, pelo Lema anterior, para todoλ ∈ R,

λn det(AB − λI) = λn det(BA− λI) ,

e, portanto, a afirmação está provada.

(ii) Se m ̸= n então AB e BA são matrizes de ordens diferentes,logo possuem polinômios característicos diferentes. Supondo, porexemplo, m > n, pelo Lema 7.2,

det(AB − λI) = (λm−n) det(BA− λI) .

Portanto, zero é raiz do polinômio característico de AB m − n

vezes a mais do que é raiz do polinômio característico de BA,

mas as outras raízes de ambos os polinômios são as mesmas, comas mesmas multiplicidades.

7.2 Resultados sobre matrizes simétricas

Nesta seção, consideramos conhecidos os fatos básicosda teoria de diagonalização de matrizes simétricas, que podemser encontrados, por exemplo, na referência [73].

Em tudo o que se segue, A é uma matriz simétrica deordem n com entradas reais, λ1 ≥ λ2 ≥ . . . ≥ λn são seus au-tovalores em ordem não crescente e {v1,v2, . . .vn} é uma baseortonormal de vetores de Rn - pensados sempre como vetores-coluna n × 1 - que são autovetores para A associados, respec-tivamente, àqueles autovalores. A notação ⟨, ⟩ indica o produtointerno canônico de Rn e ∥.∥, a norma Euclidiana.

7.2.1 Princípio de Rayleigh

As Proposições 7.2 e 7.3, conhecidas como Princípio deRayleigh, caracterizam os autovalores de A como valores máxi-mos de uma forma quadrática restrita à esfera unitária de Rn

com centro na origem. Estes resultados constituem uma téc-nica frequentemente empregada para encontrar grafos com índicemáximo e índice mínimo em classes particulares de grafos. Nassuas demonstrações nos baseamos em [35].

Proposição 7.2. λ1 = max∥x∥=1

⟨Ax,x⟩ .

7.2 Resultados sobre matrizes simétricas 187

Demonstração: Seja P a matriz ortogonal cujas colunas são osvetores v1,v2, . . .vn. Sabemos que PTA = EPT , onde E =

diag(λ1, λ2, . . . , λn) é a matriz diagonal dos autovalores de A.Seja x ∈ Rn com ∥x∥ = 1. Sendo P matriz ortogonal, o vetory = PTx = [y1 y2 . . . yn]

T é também unitário e

⟨Ax,x⟩ = ⟨PTAx, PTx⟩ =

= ⟨Ey,y⟩ = λ1y21 + λ2y

22 + . . .+ λny

2n ≤ λ1⟨y,y⟩ = λ1 .

Como λ1 = ⟨Av1,v1⟩, o resultado está provado.

Corolário 7.1. λ1 = maxx̸=0

⟨Ax,x⟩⟨x,x⟩

e o valor máximo é atingido somente em autovetores unitáriosassociados ao autovalor.

Lembrando que ⟨Avi,vi⟩ = λi, para todo i, 1 ≤ i ≤ n,

podemos usar um raciocínio análogo ao da prova acima parageneralizar a Proposição 7.2 para os demais autovalores de A.De fato, vale a

Proposição 7.3. Para cada i, 1 ≤ i ≤ n,

λi = max{⟨Ax,x⟩ | ∥x∥ = 1 e x⊥vj, 1 ≤ j < 1 } ,

sendo o valor máximo atingido para autovetores unitários de A

associados ao autovalor λi.

Demonstração: Fixados i, 1 ≤ i ≤ n e x ∈ Rn tal que ∥x∥ = 1

e x⊥vj, 1 ≤ j < 1, tomamos como antes y = PTx. Então∥y∥ = 1, e para cada j, 1 ≤ j < i, ⟨y, PTvj⟩ = ⟨PTx, PTvj⟩ =

188 Apêndice

⟨x,vj⟩ = 0, sendo que PTvj = ej, o j-ésimo vetor da basecanônica de Rn. Logo, se y = [y1 y2 . . . yn]

T obtemos

⟨Ax,x⟩ = ⟨Ey,y⟩ = 0+λiy2i + . . .+λny

2n ≤ λi⟨y,y⟩ = λi .

Corolário 7.2. Para cada i, 1 ≤ i ≤ n,

λi = max

{⟨Ax,x⟩⟨x,x⟩

| x ̸= 0 e x⊥vj, 1 ≤ j < i

},

sendo o valor máximo atingido em autovetores unitários associ-ados ao autovalor.

Corolário 7.3. Para cada i, 1 ≤ i ≤ n,

λi = min

{⟨Ax,x⟩⟨x,x⟩

| x ̸= 0 e x⊥vj, i < j ≤ n

},

sendo o valor mínimo atingido em autovetores unitários associ-ados ao autovalor.

Demonstração: Basta utilizar o raciocínio anterior para a matriz−A.

7.2.2 Teorema de Entrelaçamento

Na desenvolvimento deste tópico seguimos [49] e [31].

Teorema 7.1. Seja M uma matriz n × m com entradas reaistal que MTM = I. Se os autovalores de MTAM são µ1 ≥ µ2 ≥. . . ≥ µm então para cada i, 1 ≤ i ≤ m, vale

λn−m+i ≤ µi ≤ λi . (7.2.1)


Demonstração: Seja {u1,u2, . . .um} uma base ortonormal deautovetores de MTAM associados, respectivamente, aos auto-valores µ1 ≥ µ2 ≥ . . . ≥ µm. Fixemos i, 1 ≤ i ≤ m e chamemosUi e Vi−1 aos subespaços de Rm gerados, respectivamente,por {u1,u2, . . . ,ui} e {MTv1,M

Tv2, . . . ,MTvi−1}. Como

dimUi + dim(Vi−1)⊥ = i + m − (i − 1) = m + 1, temos que

Ui ∩ (Vi−1)⊥ contém algum vetor wi não nulo. Assim, para cada

j, 1 ≤ j ≤ i−1, ⟨Mwi,vj⟩ = 0 pois ⟨wi,MTvj⟩ = 0. Além disso,

⟨AMwi,Mwi⟩ = ⟨MTAMwi,MTMwi⟩ e ⟨Mwi,Mwi⟩ =

⟨wi,wi⟩. Daí e pelo Princípio de Rayleigh (7.2 e 7.3), chegamosa

λi ≥⟨AMwi,Mwi⟩⟨Mwi,Mwi⟩

=⟨MTAMwi,wi⟩⟨wi,wi⟩

≥ µi .

Para a outra desigualdade em 7.2.1, usa-se o mesmo argumentopara as matrizes −A e −MTAM .

As desigualdades 7.2.1 são conhecidas como desigual-dades de Cauchy. Quando satisfeitas, dizemos que os autova-lores de A entrelaçam os de MTAM .

Mostra-se que uma n×m matriz M com entradas reaissatisfaz MTM = Im se e somente se suas colunas formam umconjunto ortonormal de vetores de Rn. Logo, se tomamos

M =

[Im

O

],

onde Im é a identidade de ordem m e O é a matriz nula deordem (n −m)×m então M satisfaz MTM = Im. Além disso,B = MTAM é uma submatriz principal de ordem m de A, istoé, uma matriz obtida de A pela retirada de n −m linhas e dascorrespondentes n −m colunas. Desta forma, obtemos a formaoriginal do Teorema de Entrelaçamento de Cauchy :

190 Apêndice

Corolário 7.4. Se B é uma submatriz principal de A então osautovalores de A entrelaçam os autovalores de B.

7.2.3 Partições equilibradas

Nesta sub-seção, consideramos X = X1∪̇X2∪̇ . . . ∪̇Xm

uma partição de {1, 2, . . . , n} em que cada |Xi| = ni > 0 edescrevemos A como matriz dos blocos correspondentes a estapartição na forma

A1,1 · · · A1,m

......

Am,1 · · · Am,m

.

Então cada bloco Ai,j tem ordem ni × nj . Seja M̃ a matrizcaracterística da partição X , ou seja, a matriz n×m em que(M̃)ij = 1 se i ∈ Xj e 0, em caso contrário. Definimos a matrizquociente de A por X como a m×m matriz B̃ em que cadaentrada Bij é a média das somas das linhas do bloco Ai,j . Então,para cada i, j, 1 ≤ i ≤ n, 1 ≤ j ≤ m, temos

(B̃)ij =1

ni1TniAi,j1nj =

1

ni(M̃TAM)ij ,

onde 1t indica o vetor [1 1 · · · 1]Tt×1. X é chamada partiçãoequilibrada (ou regular) quando em cada bloco, a soma daslinhas (e colunas) é constante. Neste caso, temos AM̃ = M̃B̃.

Corolário 7.5. Seja B̃ a matriz quociente de A em relação àpartição X como acima. Então os autovalores de A entrelaçamos autovalores de B̃.

Demonstração: Pela construção feita acima, M̃ é exatamentea n × m matriz de incidência vértice-bloco da partição X . Se


c1, c2, , . . . , cm são as colunas de M̃ , ponhamos

M =[

1n1

c1 | 1n2

c2 | · · · | 1nm

cm

].

Temos então que MTM = I e MTAM = B̃. Logo o resultadosegue do Teorema 7.1.

Teorema 7.2. Consideremos X uma partição equilibrada de{1, 2, . . . , n} onde em cada bloco Ai,j a soma de cada linha éconstante e igual a bij. Se B = (bij)m×m então o espectro de B

está contido no espectro de A, levando em conta as multiplici-dades.

Demonstração: Seja x = [x1 x2 · · · xm]T autovetor de B asso-ciado a um autovalor µ. Então o vetor

y =

x11n1

x21n2

...xm1n1

é um autovetor de A associado ao mesmo autovalor e o resultadoestá provado.

7.2.4 Teorema de Sylvester para a inércia

Neste tópico, seguimos [69].

Primeiramente, lembramos que todos os autovalores deA são reais, pois A é matriz simétrica.

192 Apêndice

Definição 7.1. O terno de inteiros não negativos (p, j, s) é ditoser a inércia da matriz A quando A possui p autovalores posi-tivos, j autovalores negativos e 0 é autovalor com multiplicidades.

Neste item, B é uma n×n matriz simétrica com entradasreais. Lembramos que, pela Definição 6.2, A e B são matrizescongruentes quando existe uma matriz não singular (isto é, in-vertível) C tal que B = CTAC. Denotamos este fato escrevendoA ∼= B. Notamos que a relação de congruência entre matrizes éuma relação de equivalência.

Lema 7.3. Se A tem inércia (p, j, s) então A ∼= E onde

E =

Ip

−IjOs×s

.

Demonstração: De fato, se {λ1, . . . , λp,−λp+1, . . . ,−λp+j , 0, . . . , 0}é o multiconjunto dos autovlaroes de A (incluindo as multiplici-dades), onde cada λi > 0, então existe uma matriz ortogonal Ptal que

PTAP = diag(λ1, . . . , λp,−λp+1, . . . ,−λp+j , 0, . . . , 0) .

Tomando C = PS, onde S = diag(λ−1/21 , . . . , λ

−1/2p+j , 1, . . . , 1)

então S é matriz não singular e

CTAC = (PS)TA(PS) = ST (PTAP ) =

= (ST diag(λ−1/21 , . . . , λ

−1/2p+j , 1, . . . , 1))S =

= diag(λ1/21 , . . . , λ

1/2p ,−λ1/2

p+1, . . . ,−λ1/2p+j , , 0 . . . , 0)S = E.


Escrevemos u ≤ 0 (respectivamente, u > 0) para in-dicar que todas as coordenadas do vetor u são não positivas(respectivamente, positivas).

Teorema 7.3 (Lei da Inércia de Sylvester). A ∼= B se e somentese A e B possuem a mesma inércia.

Demonstração: Suponha B ∼= A e seja (q, k, t) a inércia de B.Pelo Lema 7.3 então B ∼= F , onde

f =

Iq

−IkOt×t

.

Como A ∼= E, E como no Lema 7.3 então F ∼= E. Logo, F

e E possuem o mesmo posto e daí, s = t. Para concluir quep = q vamos raciocinar indiretamente: para isto, suponhamospor absurdo que p > q. Seja K uma matriz n × n não singulartal que

F = KTEK.

Podemos escrever K =[Xn×q | Yn×(n−q)

]. Sejam U =

Im(Y ) o subespaço de Rn gerado pelas colunas de Y e V, osubespaço gerado pelos vetores e1, e2, . . . , ep da base canônicade Rn. Então

dim(U∩V) = dimU+dimV−dim(U+V) = (n−q)+p−n = p−q > 0.

Logo existe vetor não nulo x = [x1 x2 · · · xn]T ∈ U ∩ V. Ora,

como x ∈ U então existe y = [y1 y2 · · · yn−q]T ∈ Rn−q tal que

Y y = x. Portanto

x = Y y = K

[0

y

].

194 Apêndice

Daí

xTEx =[0T yT

]KTEK

[0

Y

]=[0T yT

]F

[0

y

]=

=

0

−y21...−y2k0

≤ 0.

Por outro lado, como x ∈ V então x = [x1 x2 · · · xp 0 · · · 0]T .Logo,

xTEx = [x1 x2 · · · xp 0 · · · 0]T

x1

...xp

0...0

> 0.

Assim, não pode ocorrer p > q. Um argumento análogo mostraque também não é possível que seja p < q. Portanto p = q. Ficaprovado que se A ∼= B então A e B possuem a mesma inércia.

Reciprocamente, supondo que A e B possuem a mesmainércia, temos pelo Lema 7.3 que A ∼= E ∼= B.

7.2.5 Teorema de Perron-Frobenius

Dado que A = (aij) e que ρ : {1, 2, · · · , n} → {1, 2, · · · , n}é uma permutação, denotamos por Aρ a matriz (aρ(i),ρ(j)). Se P


é uma matriz obtida permutando-se as linhas da matriz iden-tidade de acordo com ρ então Aρ = PAPT ; segue que Aρ e A

possuem os mesmos autovalores e que se v é um autovetor de A

então vρ é um autovetor de Aρ.

Neste tópico, seguimos a apresentação bastante didáticade [35] para a prova do Teorema de Perron-Frobenius dada em[62]. Como referência, indicamos também [31].

Dizemos que uma matriz C é não-negativa (respecti-vamente, positiva) quando suas entradas são não negativas. In-dicamos este fato escrevendo C ≥ O (respectivamente, C > O).

Definição 7.2. Dizemos que a matriz simétrica A é irredutívelse não existe permutação ρ tal que

Aρ =

[X Z

O Y

],

onde X e Y são matrizes quadradas. Em caso contrário, A édita uma matriz redutível.

Lema 7.4. Se a matriz A é não negativa e A irredutível então(I+A)n−1 > 0, ou equivalentemente, I+A+A2+. . .+An−1 > 0.

Demonstração: Ver, por exemplo, [69].

Proposição 7.4. Se G é um grafo conexo com n vértices e A ésua matriz de adjacência então A é irredutível.

Demonstração: Como G é conexo, para cada par i, j, 1 ≤ i, j ≤n, existe pelo menos um caminho (logo, uma cadeia) ligando ovértice vi ao vértice vj , que terá comprimento no máximo iguala n− 1. Pela Proposição 2.2, isto significa que pelo menos uma

196 Apêndice

das matrizes simétricas Ak, onde 0 ≤ k ≤ n − 1 tem a entradaij positiva, para cada par i, j, 1 ≤ i, j ≤ n. Pelo Lema acima, amatriz A é irredutível.

Teorema 7.4 (Teorema de Perron-Frobenius). Suponhamos queA seja matriz não negativa, irredutível e com autovalores λ1 ≥λ2 ≥ . . . ≥ λn. Então

(i) λ1 > 0 e existe um autovetor associado positivo;

(ii) λ1 > λ2;

(iii) |λi| ≤ λ1, para todo i ∈ {1, 2, . . . , n}.

Demonstração: (i): Como A é não negativa então tr(A) ≥ 0.Como tr(A) =

∑i λi então λ1 ≥ 0. Vamos mostrar que existe

autovetor positivo associado a λ1 e, em seguida, que λ1 > 0.Seja u = [u1 u2 · · · un]

T um autovetor unitário associado a λ1.Então, pela Proposição 7.2 e Corolário 7.1

λ1 = uTAu =

n∑i=1

n∑j=1

aijuiuj ≤n∑

i=1

n∑j=1

aij|ui||uj | ≤ λ1.

Ou seja, o vetor v = [|u1| |u2| · · · |un|]T é um autovetor nãonegativo e unitário associado a λ1.

Suponhamos que existam coordenadas nulas em v. Sejaentão ρ uma permutação de {1, 2, . . . , n} tal que |uρ(i)| > 0 paratodo i ≤ m e |uρ(i)| = 0 para todo i, m < i ≤ n. Escrevamos

Aρ =

[X Z

T Y

]e vρ =

[u′

0

],


onde u′ = [|uρ(1)|, |uρ(2)|, · · · , |uρ(m)|]T e X e Y são matrizesquadradas. Então[

X Z

T Y

][u′

0

]=

[λ1u

′

0

],

e portanto, necessariamente, T = O, acarretando ser A matrizredutível, o que é absurdo. Consequentemente, v > 0. Devemosnotar que supondo λ1 = 0, obtemos da mesma forma que T = O,contrariando o fato de ser A matriz irredutível.

(ii) Suponhamos que λ1 tem multiplicidade geométrica (logo al-gébrica, já que A é simétrica) maior ou igual a 2. Podemos entãoescolher u e v dois autovetores ortonormais associados a λ1 e apartir deles, definir outros autovetores associados a λ1 pondo

u′ =

u1 + |u1|u2 + |u2|

...un + |un|

e v′ =

v1 + |v1|v2 + |v2|

...vn + |vn|

,

onde ui e Vi são as coordenadas de u e v, respectivamente. Entãoui+ |ui| ≥ 0 para todo i ∈ {1, 2, . . . , n}, e portanto, ui+ |ui| > 0

para todo i, i = 1, . . . , n; de fato, caso contrário, usando amesma estratégia da prova de (i), concluiríamos que a matriz A

não seria irredutível. Da mesma forma, vi + |vi| > 0 para todoi, i = 1, . . . , n. Mas isto nos diz que os vetores ortonormais u ev têm todas as coordenadas positivas, o que é absurdo. Assim,a multiplicidade de λ1 é igual a 1 e λ1 > λ2.(iii) Fixemos i, 1 ≤ i ≤ n. Notemos que, se v(i) = [v1 v2 . . . vn]

T

é um autovetor unitário de A associado a λi então

|λi| = |v(i)TAv(i)| =

∣∣∣∣∣n∑

k=1

n∑l=1

aklvkvl

∣∣∣∣∣ ≤n∑

k=1

n∑l=1

akl|vk||vl| ≤ λ1.

198 Apêndice

Logo |λi| ≤ λ1 para todo i, 1 ≤ i ≤ n.

199

Índice

J , 44Mn, 381 = [1, · · · , 1]T , 38índice de G, 28índice do Laplaciano, 100árvore, 17árvore geradora, 87Möbius Ladder, 51cocktail party graph, 45join de grafos, 19

aresta, 13autovalor do grafo G, 28autovalore simples, 170

cadeia, 15cadeia aberta, 16cadeia fechada, 15caminho, 16caracterizado pelo seu espec-

tro, 54centopeia, 155centralidade de autovetor do

um vértice, 36ciclo, 16ciclo hamiltoniano, 60componente conexa, 16

comprimento de um caminhoou de um ciclo, 16

conectividade algébrica, 100conectividade de arestas, 103conectividade de vértices, 103conjunto de corte, 105corte maximal de um grafo,

105cubo, 68

desigualdades de Cauchy, 189diâmetro, 21distância entre um par de vér-

tices, 21

energia Laplaciana de um grafo,121

energia de um grafo, 57entrelaçamento de autovalo-

res, 189espectro de G, 28espectro do Laplaciano de um

grafo, 82

floresta, 17

grafo, 13grafo k-partido, 17

200 Índice

grafo autocomplementar, 119grafo bipartido, 17grafo bipartido completo, 18grafo cúbico, 24grafo circulante, 47grafo complementar de um

grafo, 18grafo completo, 15grafo conexo, 16grafo de Moore, 22grafo de Petersen, 22, 66, 77grafo desconexo, 16grafo estrela, 119grafo exato, 108grafo hiperenergético, 61grafo regular de grau k ou

k-regular, 14grafo threshold, 157, 158grafo totalmente desconexo,

54grafo tripartido, 17grafo trivial, 13grafo união, 19grafo-linha, 18grafos, 13grafos coespectrais, 53grafos isomorfos, 52grafos moleculares, 57grafos simples, 13grau de um vértice, 13

grau mínimo, 20grau máximo, 20grau médio de um grafo, 20

hiperoctaedro, 45

inércia de matriz, 192incerteza coespectral, 136invariantes de grafo, 52isomorfismo, 52

Laplaciano de um grafo, 81

matriz de incidência com re-speito a uma dadaorientação, 83

matriz característica da par-tição, 190

matriz circulante, 48matriz de adjacência, 28matriz de incidência, 71matriz diagonal dos graus,

81matriz irredutível, 195Matriz Laplaciana, 81matriz Laplaciana, 81matriz Laplaciana sem sinal,

124matriz não negativa, 195matriz positiva, 195matriz quociente, 190matriz redutível, 195

Índice 201

matrizes congruentes, 145, 192menor principal, 30

partição equilibrada, 190partição regular, 190pipa, 67polinômio característico de

G, 28polinômio característico da

matriz Laplaciana semsinal, 124

Princípio de Rayleigh, 186produto cartesiano de grafos,

20

raio espectral de um grafo,36

semirregular, 109soma de grafos, 19subgrafo, 14subgrafo induzido, 14submatriz principal, 30

Teorema de Entrelaçamentode Cauchy, 189

Teorema de entrelaçamentopara matriz Lapla-ciana, 86

Teorema do entrelaçamento,34

traço, 158

triângulo, 16

vértice, 13vértices adjacentes, 13vetor corretor, 110

Documents

Teoria Espectral de Grafos - Uma Introdução III … · Figura 2 – Um grafo 4-regular. •grafo completo: É o grafo no qual quaisquer dois vértices distintos são adjacentes