Tpicos em Teoria dos Grafos — Mtodos da Algebra Linear em Teoria de Grafos

Tópicos em Teoria dos Grafos
— Métodos da Álgebra Linear em Teoria de Grafos —

Jair Donadelli

dezembro de 2005

Sumário

1 Grafos extremais sem triângulos
2 Grafos extremais sem K^p
3 Coloração de vértices
4 α e χ típicos
5 Matrizes
6 Autovalores e autovetores
7 Matrizes simétricas e o Teorema Espectral
8 Teorema de Courant-Fischer e Teorema de Perron-Frobenius
9 Teoria Espectral de Grafos
9.1 Grau
9.2 Subgrafos
9.3 Conexidade
9.4 Grafos bipartidos
10 α,χ,ω,λ
11 Distribuição das arestas e λ
11.1 Grafos d-regulares
11.2 Grafos não-regulares
12 Grafos Expansores
13 λ₁, λ típicos
13.1 e(G) e r_G(C⁴) típicos
13.2 Número de arestas típico.
14 Laplaciano
14.1 Autovalores da matriz laplaciana

Resumo

Estas são notas de aula da disciplina optativa CI084–Tópicos em Teoria dos Grafos que foi ofertada no segundo semestre de 2005 para o Bacharelado em Ciência da Computação na UFPR. Mais informações sobre a discplina podem ser obtidas em

http://www.inf.ufpr.br/jair/COURSES/ttg.html

Aqui apresentamos os principais ferramentas da Álgebra Linear para a Teoria dos Grafos e as técnicas elementares para a análise estrutural de grafos a partir dos autovetores e autovalores da matriz de adjacências dos grafos.

Parte das notas foram redigidas pelos alunos do curso, aqui apresento-as revisada e com algumas alterações que, acredito, melhoram a apresentação. A redação das notas foram parte da avaliação e em cada seção desta nota apresento o aluno que foi o responsável pela seção. Agradeço ao empenho do alunos do curso: Ander Conselvan de Oliveira, Everson Carlos Mauda, Gustavo Baggio, Leonardo Ferreira da Silva Boiko, Luiz Alberto A Santos Jr, Renan Fischer E. Silva, Ricardo Fabiano Samila, Tiago Sak, Tiago Vignatti.

Jair

1 Grafos extremais sem triângulos

Suponha que G = Gⁿ é um grafo de ordem n que não contenha três vértices formando um triângulo. Vamos determinar o número máximo de arestas em G.

Seja A ⊂ V (G) um conjunto independente em G de cardinalidade α(G) (máxima).

Como G não contém triângulos temos

d (v) ≤ α(G), paratodov ∈ V (G). G

(1)

Dessa forma

|E (G)| ≤ ∑ d(u) ≤ α(G )|A-| = α(G )(n - α (G )), -- u∈A

(2)

e da desigualdade entre média geométrica e média aritmética concluímos que

( )2 2 |E (G )| ≤ α(G)-+-(n---α-(G-))- = n--. 2 4

(3)

Assim provamos o seguinte resultado.

Teorema. Se G é um grafo sem triângulos então |E(G)|≤ 2
|V(G4)| . ♦

Um candidato natural a grafo extremal sem K³, ou seja, um grafo sem triângulo e com o maior número possível de arestas, é o grafo bipartido completo. Suponha que A e B são partes de um grafo bipartido com |A|-|B|≥ 2. Note que transferindo um vértice de A para B temos um novo grafo bipartido com |A|-|B| arestas a mais.

Mostraremos que esse é o único grafo extremal na próxima seção.

Exercício 1. Denotamos por K_{n₁,n₂,…,n_p-1} o grafo (p-1)-partido completo onde as partes têm cardinalidades n₁,n₂,…,n_p-1. Mostre que dentre os grafos (p - 1)-partidos completos com n vértices o número máximo de arestas é atingido quando |n_i - n_j|≤ 1 para todos i,j ∈ [p - 1].

Em 1941, Paul Turán provou que esse grafo é extremal com relação a conter K^p. Mais que isso, esse grafo é único¹ com essa propriedade. Esse grafo é conhecido como de grafo de Turán

Exercício 2. Mostre que para inteiros n, p > 1, se n = (p - 1)k + r, com 0 ≤ r < p - 1, então o número de arestas no grafo de Turán é

( ) ( ) ( ) 1- p--2- 2 2 r p---2 n 2 p- 1 (n - r )+ 2 ≤ p - 1 2 .

(4)

2 Grafos extremais sem K^p

Teorema 3. Para todos n, p > 1 o número de arestas num grafo de ordem n extremal sem K^p é dado por (4). Ainda, todo grafo extremal Gⁿ que não contém K^p é o grafo de Turán.

Demonstração. Seja Gⁿ um grafo extremal sem K^p. Vamos mostrar que em Gⁿ não existem três vértices u,v,w tais que uw ∈ E(G), vu ⁄∈ E(G) e vw ⁄∈ E(G).

Suponha o contrário e vamos derivar uma contradição em dois casos. Primeiro, vamos supor que d(v) < d(u). Nesse caso removemos o vértice v, ou seja consideramos G - v = G[(V \{v}], e nesse grafo duplicamos o vértice u: o conjunto de vértices fica V (G-v) ∪{u′}, supondo que u′é um vértice novo, e ligamos u′ a todos os vértices de N(u). Esse grafo resultante tem ordem n e d(u) - d(v) arestas a mais que Gⁿ; também (exercício) não contém K^p, um absurdo pois Gⁿ é extremal.

Portanto d(v) ≥ d(u) e, analogamente, d(v) ≥ d(w). Nesse caso, removemos u e w do grafo G e duplicamos v em v′ e em v′′. Novamente, o grafo obtido tem mais arestas que Gⁿ e não contém K^p, um absurdo.

Com esse fato concluímos que a relação u ~ v dada por uv ⁄∈ E(G) é de equivalência sobre V (G). Claramente, as classes de equivalência são conjuntos independentes. Do fato de Gⁿ ser extremal concluímos que é um grafo (p - 1)-partido completo. ♦

O caso genérico de grafo extremal sem H, para um grafo H fixo, foi resolvido por Erds e Stone. O Teorema de Erds–Stone, algumas vezes chamado Teorema Fundamental da Teoria Extremal de Grafos, foi provado em 1946 e diz que se n for suficientemente grande, então um grafo de ordem n com uma fração ρ > (p - 2)∕(p - 1) das arestas contém não só um K^p mas um K^p(t), isto é, o grafo p-partido completo com t vértices em cada classe, para todo inteiro positivo t.

Teorema. Dados inteiros p ≥ 2 e t ≥ 1 e um real 0 < ρ < 1, existe n₀ > 0 tal que todo grafo com n ≥ n₀ vértices e pelo menos

( ) ( ) 1- p---2 (n2 - r2) + r + ρn2 2 p - 1 2

arestas, contém uma cópia do K^p(t), onde r = n modp - 1.

Em outras palavras, o número de arestas no grafo extremal é

( ) ( ) p---2 n p - 1 + o(1) 2 ,

onde o(1) denota uma função f(n) tal que lim_n→∞f(n) = 0.

O Teorema de Erds–Stone tem o seguinte, bastante interessante, corolário.

Corolário 1. Para todo grafo H, o número de arestas num grafo extremal sem H denotado por ex(n,H) satisfaz

ex (n,H ) χ (H) - 2 lnim→∞ ---(n)-- = χ-(H)---1, 2

onde χ(H) é o menor número de partes numa partição de V (H) em conjuntos independentes.

3 Coloração de vértices

Uma p-coloração dos vértices de G é uma partição V (G) = V ₁ ∪V ₂ ∪ ⋅⋅⋅ ∪V _p. Se as classes V _i são conjuntos independentes então dizemos que a coloração é própria.

O número cromático de G é definido por

χ (G ) = min{p ∈ ℕ : G admite uma p- colora¸c˜ao pr´opria}.

Proposição 4. Se ω(G) é a ordem do maior subgrafo completo em G

χ(G ) ≥ ω (G ).

♦

Proposição 5. Para todo G = Gⁿ

χ(G) ≥ --n--. α (G )

♦

Proposição 6. Para todo G

∘ ------------ χ(G) ≤ 1-+ 2|E(G )|+ 1. 2 4

Demonstração. Dada uma χ(H)-coloração própria teremos pelo menos uma aresta entre vértices de cada par de classes de cor. Assim

( ) 2 |E (G)| ≥ χ(G ) = χ(G-)---χ(G-), 2 2

donde concluímos o limitante superior enunciado pois derivamos da desigualdade acima

( )2 1- 1- 2|E (G )|+ 4 ≥ χ(G )- 2 .

♦

Teorema 7. Para todo G = Gⁿ

χ(G ) ≤ Δ (G) + 1.

Demonstração. A prova é por indução em n. Se n = 1 então o enunciado do teorema vale, trivialmente.

Seja G um grafo de ordem n e seja v um vértice qualquer. tomemos H = G - v.

Pela hipótese indutiva temos que χ(H) = k ≤ Δ(H) + 1 ≤ Δ(G) + 1. Seja {V ₁,V ₂,…,V _k} uma coloração própria de H.

Se k < Δ(G) + 1 então {{v},V ₁,…,V _k}é uma coloração própria de G com ≤ Δ(G) + 1 cores.

Se k = Δ(G)+1 então existe uma cor i que não ocorre entre os vizinhos de v pois d_G(v) ≤ Δ(G). Dessa forma podemos tomar a coloração própria {V ₁,V ₂,…,V _i ∪{v},…,V _k}. ♦

Um pouco mais pode ser dito em certos casos:

Teorema (teorema de Brooks). Se G não é um circuito ímpar nem um grafo completo então χ(G) ≤ Δ(G). ♦

Apesar do resultado mostrado acima, chamamos a atenção para do fato de Δ(G) - χ(G) poder ser arbitrariamente grande, como demonstra o K_1,n.

4 α e χ típicos

Por típico, entendemos resultados do tipo: 99,9% dos grafos com 1024 vértices têm α < 22 e 99,9% dos grafos com 1024 vértices têm χ > 46. Esses enunciados serão corolários de um resultado mais geral que provaremos a seguir.

Fixamos V = [n] e definimos (n) como o conjunto de todos os grafos sobre V . Claramente |(n)| = 2^N, onde N = ( )
n2 .

Denotamos por _k(n) o conjunto dos grafos G ∈(n) tais que α(G) ≥ k. Para estima a cardinalidade desse conjunto, fixamos X ⊂ [n] de cardinalidade k. Os grafos de (n) nos quais X é um conjunto independente podem ser identificados numa relação de um-para-um com os subconjuntos de V ⁽²⁾ \ X⁽²⁾, onde X⁽²⁾ é o conjunto de todas as arestas sobre X. Segue-se que

(n ) N- k |Qk (n)| ≤ k 2 (2),

donde deduzimos

k(k-1) |Qk-(n)|≤ nk2 ---2-- |G(n)|

e tirando o logaritmo de ambos os lados

( ) 2lg |Qk(n-)| ≤ k lg(n )- k(k - 1) = k (- k + lg(n) + 1). |G (n)|

Tomando k = ⌈(2+ ε)lg(n)⌉

( ) |Qk(n)| 2lg |G (n )| ≤ ⌈(2 + ε)lg(n )⌉(- (2 + ε)lg(n) + lg(n )+ 1) = ⌈(2 + ε)lg(n )⌉ (- (1+ ε) lg(n) + lg(n) + 1) → - ∞

conforme n →∞. Ou seja

Teorema 8. Por menor que seja ε > 0

α(G) < ⌈(2+ ε) lg n⌉

para quase todo G ∈

(n). ♦

Corolário 2. Por menor que seja ε > 0

-----n------ χ (G) > ⌈(2+ ε)lgn ⌉

para quase todo G ∈

(n). ♦

Acima, para quase todo significa que |(n)|∕|(n)|→ 1 conforme n →∞, onde é o subconjunto dos grafos que satisfazem a propriedade de interesse (no nosso caso, número de independência pequeno e número cromático alto).

Exercício 9. Por menor que seja ε > 0

ω(G) ≥ (2+ ε) lg n

para quase todo G ∈

(n).

5 Matrizes

Vamos assumir que as matrizes são sempre quadradas n × n a menos que seja mencionado o contrário. Denotamos por A = (a_i,j) a matriz cuja entrada na i-ésima linha e j-ésima coluna é a_i,j ∈ ℂ.

Um vetor v é uma matriz coluna

( a ) | 1| v = || a2.|| ( ..) an

e também denotamos matrizes através dos seus vetores colunas

( ) a1,1 a1,2 ⋅⋅⋅ a1,n || a2,1 a2,2 ⋅⋅⋅ a2,n|| A = (v1,v2,⋅⋅⋅,vn) = || ... ... ... ... || . |( a a ⋅⋅⋅ a |) n,1 n,2 n,n

A transposta da matriz A é a matriz

( ) ( ) v1T a1,1 a2,1 ⋅⋅⋅ an,1 | v2T| || a1,2 a2,2 ⋅⋅⋅ an,2|| AT = || . || = || ... ... ... ... || , ( .. ) |( |) vnT a1,n a2,n ⋅⋅⋅ an,n

e a conjugada-transposta é a matriz

( ---- ---- ----) a1,1- a2,1 ⋅⋅⋅ an,1 || a1,2 a2,2 ⋅⋅⋅ an,2|| A* = || ... ... ... ... || , |( ---- ---- ----|) a1,n a2,n ⋅⋅⋅ an,n

onde z = x + iy = x - iy é o conjugado de um número complexo.

Dizemos que a matriz A é invertível se existe uma matriz B tal que

(1 0 ⋅⋅⋅ 0) |0 1 ⋅⋅⋅ 0| || . . . .|| AB = BA = Id = || .. .. .. ..|| , (0 0 ⋅⋅⋅ 1)

e dizemos que A e B são semelhantes, denotado por A ~ B, se existe uma matriz invertível P tal que B = P^-1AP. A matriz A é diagonalizável se for semelhante a uma matriz diagonal

( ) |a1 0 ⋅⋅⋅ 0| | 0 a2 ⋅⋅⋅ 0| diag(a1,a2,...,an) = || ... ... ... ...|| . |( 0 0 ⋅⋅⋅ a |) n

O traço de uma matriz é a soma dos elementos da diagonal

∑n tr(A) = ai,i i=1

e o determinante

∑ det(A) = (sinal(σ))a a ⋅⋅⋅a σ 1,σ(1) 2,σ(2) n,σ(n)

onde a soma é sobre toda permutação σ: {1,2,…,n}→{1,2,…,n}. Equivalentemente,

∑n det(A ) = (- 1)1+ja1,jdet(A1,j), onde A1,j = (ai,ℓ)i⁄=1,ℓ⁄=j. j=1

Exercício 10. Mostre

tr(AB) = tr(BA).
(AB)^* = B^*A^*.
det(A^T) = det(A).
det(AB) = det(A)det(B).
Se A ~ B então det(A) = det(B).
Se A e B são matrizes quadradas então $(A C ) det 0 B = det(A)det(B),$ onde 0 é a matriz nula.

Teorema 11. S ão equivalentes

A é invertível;
Ax = 0 tem apenas a solução trivial;
os vetores coluna de A são linearmente independentes;
det(A)≠0.

Esboço de uma prova. Se A é invertível então Ax = b tem única solução, a saber x = A^-1b, portanto (i)⇒(ii). Pelo item (2) do exercício acima det(A)≠0, logo (i)⇒(iv).

Como Ax é uma combinação linear das colunas de A a solução trivial única significa independência linear dos vetores coluna, e vice-versa, portanto (ii) e (iii) são equivalentes.

Tome o cofator de a_i,j

cof(ai,j) = (- 1)i+jdet(Ai,j), onde Ai,j = (ak,ℓ)k⁄=i,ℓ⁄=j

e é deixado como exercício mostrar que B dada por

bi,j = cof(aj,i) det(A)

é a inversa de A, dado que det(A)≠0. Dessa forma (iv)⇒(i).

Pra terminar vamos mostrar que (iii)⇒(i). Considere a transformação linear

T : ℝn → ℝn x ↦→ Ax,

como as colunas são linearmente independentes a dimensão da imagem de T é n, portanto T é sobrejetora. Como domínio e imagem têm a mesma dimensão T é bijetora. Por ser bijetora admite uma inversa T^-1 e assim A é invertível. ♦

6 Autovalores e autovetores

Seja A uma matriz quadrada n × n sobre ℂ. Dizemos que λ ∈ ℂ é autovalor se existe um vetor v≠0 tal que

Av = λv.

(5)

Dizemos que v é um autovetor associado ao autovalor λ. Um autovalor de uma matriz não é único, tampouco os autovetores associados a um autovalor.

A equação (5) acima pode ser escrita na forma

(A - λId)v = 0,

e, pelo Teorema 11, para que sejam admitidas soluções não-nulas, a matriz denotada pelo termo A - λId deve ser não-invertível, ou seja,

det(A - λId) = 0.

O determinante det(A - λId) é um polinômio em λ denominado polinômio característico de A:

pA(x) = det(A - xId),

(6)

cujo grau corresponde à ordem da matriz A (ou seja, n). Portanto, a condição para a existência de autovetores associados a um autovalor λ pode ser expressa por

pA(λ) = 0 ⇔ ∃v, Av = λv.

Pelo Teorema Fundamental da Álgebra, toda matriz possui autovalor λ ∈ ℂ. Note que se A é real e λ é real, então podemos tomar autovetores v reais.

Proposição 12. Toda matriz tem autovalor λ ∈ ℂ. ♦

Exemplo 13. A matriz

( ) ( 1 1) A = - 1 1

tem polinômio característico

( ( ) ( ) ) ( ) 1 1 1 0 1 - x 0 2 pA(x) = det( ( - 1 1) - x (0 1) ) = det( - 1 1- x) = 2- 2x+x ,

como o discriminante é Δ = -4, os autovalores são 1 + i e 1 - i.

Exemplo 14. A matriz

( ) - 3 4 A = ( - 1 2)

tem autovalores λ₁ = 1 e λ₂ = -2.

Os autovetores associados a λ₁ satisfazem

( ) ( - 3 4 ( ) ( ) { - x + y = 0 ( - 1 2) x = 1 x = ⇒ - x + y = 0 , y y (

como x = y, o conjunto de autovetores é

{ (x) } Vλ1 = x : x ∈ ℝ* .

Analogamente, os autovetores associados a λ₂ são

{ ( ) } V λ2 = 4y : y ∈ ℝ* . y

Exemplo 15. Para a matriz

( ) 1 0 A = ( 1 - 2)

temos autovalores λ₁ = 1, com autovetores V _λ₁ = { (3a)
a

: a ∈ ℝ^*}; e λ₂ = -2, com autovetores V _λ₂ = { ( )
0b

: b ∈ ℝ^*}.

Exemplo 16.

( ) 3 0 - 4 A = || 0 3 5 || ( 0 0 - 1)

O polinômio característico p_A(x) = (3 - x)²(-1 - x) admite como raízes (3,3,-1). Portanto os autovalores são λ₁ = 3 com multiplicidade 2 e λ₂ = -1 com multiplicidade 1.

Os autovetores associados a λ₁ satisfazem

( ) 3 0 - 4 ( x) ( x) ( 3y - 7z = 0 || 0 3 5 || ( ) ( ) { ( 0 0 - 1) y = 3 y =⇒ ( 3x - 2z = 0 , z z 3x + 3y + 4z = 0

a partir do que se obtém os autovetores

( ( ) ) { x *} V λ1 = ( ( y) : x,y ∈ ℝ ) . 0

Os autovetores associados a λ₂ = -1 são

( ( ) ) { ( 5z) *} Vλ2 = ( 4z ,z ∈ ℝ ) . z

Exemplo 17.

( ) 3 - 3 - 4 |0 - 1 5 | A = |(0 0 - 1|)

tem polinômio característico p_A(x) = (3-x)(-1-x)², com raízes (3,-1,-1), portanto autovalores λ₁ = 3 com multiplicidade 1 e λ₂ = -1 com multiplicidade 2.

Autovetores associados a λ₁

( ( ) ) { x } V λ1 = ( ( 0) : x ∈ ℝ*) . 0

Autovetores associados a λ₂

( ( 31 ) ) { (- 165z) *} Vλ2 = ( - 4z : z ∈ ℝ ) . z

A união do conjunto V _λ dos autovetores associados a λ com o vetor nulo 0 define um subespaço vetorial que também denotamos por V _λ. Por exemplo, se A é uma matriz real e λ₁ ∈ ℝ um autovalor então

3 Vλ = {v ∈ ℝ : Av = λv }

é um subespaço do ℝ³.

A dimensão dimV de um subespaço V é o menor número de vetores que geram o subespaço, por exemplo

( ( ) ) { (x ) 3 } Vλ1 = ( y ∈ ℝ : x,y ∈ ℝ) 0

tem dimensão dimV _λ₁ = 2.

Se λ é autovalor de A, então V _λ = {v ∈ ℂⁿ : Av = λv}é subespaço de ℂⁿ (denominado auto-espaço associado a λ)

A multiplicidade geométrica de λ, mg(λ), é a dimensão do auto-espaço associado ao autovalor λ, dimV _λ. A multiplicidade algébrica de λ, ma(λ), é a multiplicidade da raiz λ de p_A(x) = 0, isto é, o número de fatores (x - λ) no polinômio característico da matriz.

Compare as multiplicidades nos exemplos 14 — 17 acima.

Proposição 18. Se λ é um autovalor de uma matriz então

mg (λ ) ≤ ma (λ).

Demonstração. Sejam A matriz, λ autovalor, V _λ ∈ ℂⁿ auto-espaço e p = mg(λ) = dimV _λ. Sejam {v₁,v₂,…,v_p} ∈ V _λ vetores linearmente independentes, e {v₁,v₂,…,v_p,u₁,…,u_n-p} o conjunto completado para uma base do ℂⁿ. Tome a matriz

( ) P = (v1,v2,...,vp, u1,...,un -p) = V U .

A matriz P é invertível, portanto existe

(--) -1 V- P = U .

Como PP^-1 = Id,

( --) (-- -- ) ( 1 0) -1 V- ( ) V-V VU | . | P P = U V U = U V UU = ( .. ) , 0 1

e de Av = λv, tem-se

( -) (--) - 1 V ( ) V ( ) P AP = U- A V U = U- AV AU ( -- -- ) ( -- ) = λV-V VAU = λId VAU . λU V UAU 0 UAU

Fazendo

( ) ( λId VAU ) x 0 ( λId- xId V-AU ) -- - |( ... |) = -- , 0 UAU 0 x 0 UAU - xId

e levando em conta que matrizes semelhantes possuem mesmos autovalores e mesmo polinômio característico, verificam-se as igualdades

-1 -- det(P AP - xId) = det(λId- xId )det(U-AU - xId) = det((λ- x )Id)det(U AU - xId ) p -- = (λ - x) det(UAU - xId),

donde λ é raiz de p_A(x) = (λ - x)^pq(x) com multiplicidade algébrica ≥ p. ♦

Lema 19. Autovetores associados a autovalores distintos são linearmente independentes.

Demonstração. Seja A matriz, λ₁,…,λ_k autovalores distintos, e v₁,…,v_k os respectivos autovetores.

A prova é por contradição. Seja

j = min{i: {v1,v2,...,vi,vi+1} ´e l.d.}.

Então

vi+1 = α1v1 + α2v2 + ⋅⋅⋅+ αivi

e multiplicando por A ambos os lados da igualdade

i i ∑ ∑ Avi+1 = αjAvj =⇒ λi+1vi+1 = αjλjvj. j=1 j=1

Por outro lado, multiplicando ambos os lados por λ_i+1, temos a igualdade

i λ v = ∑ α λ v , i+1 i+1 j=1 j i+1 j

e portanto

i ∑ 0 = (λj - λi+1)αjvj j=1 = (λ1 - λi+1)αivi + (λ2 - λi+1)α2v2 + ⋅⋅⋅+ (λi - λi+1)αivi.

Isso implica que (λ_j -λ_i+1)α_j = 0 (∀j), e como o termo (λ_j -λ_i+1) não pode ser nulo, por se tratar de um autovalores distintos, tem-se

αj = 0 (∀j) ⇒ vi+1 = 0,

portanto v_i+1 não é autovetor. ♦

Lema 20. Uma matriz A é diagonalizável se, e somente se, tem n autovetores linearmente independentes.

Demonstração. Seja A matriz diagonalizável, então existe P invertível e D = diag(x₁,…,x_n) diagonal tal que

( ) | x1 0 | A = P -1( ... ) P 0 xn

Observe que A = P^-1DP ⇔ AP^-1 = P^-1D.

A condição “A diagonalizável ⇒ A tem n autovetores l.i.” é provada pelas equações abaixo:

-1 P = (u1,...,un), onde {u1,...,un } l.i. pois a matriz ´e invert´ivel AP -1 = (Au1, Au2,...,Aun ) - 1 P D = (x1u1,x2u2, ...,xnun ) ⇒ Aui = xiui (∀i),

portanto u_i são autovetores.

Prova-se a recíproca considerando a matriz invertível P = (u₁,…,u_n), onde u_i são n autovetores l.i.,

AP = (Au1,Au2, ...,Aun ) = (λ1u1,λ2u2,...,λnun ) ( ) | λ1 0 | = (u1,u2,...,un)( ... ) 0 λn = P D

portanto A = PDP^-1, ou seja, A é semelhante a uma matriz diagonal. ♦

Teorema 21. Se uma matriz A é diagonalizável, então ma(λ) = mg(λ) para todo autovalor λ de A.

Demonstração. Exercício. ♦

Exercício 22. Mostre que se A ~ B então p_A(x) = p_B(x).

7 Matrizes simétricas e o Teorema Espectral

Seja A uma matriz quadrada n × n sobre ℝ. Dizemos que A é simétrica se

T A = A .

Por exemplo, a matriz de adjacências de um grafo é uma matriz simétrica.

Teorema 23. Se A é uma matriz simétrica então seus autovalores são reais.

Demonstração. Seja λ um autovalor de A e v autovetor de A associado ao autovalor. Por um lado temos

* * * v Av = v λv = λv v,

e por outro,

v*Av = (A*v)*v = (Av )*v = (λv)*v = λv*v.

Portanto, λ = λ, ou seja λ ∈ ℝ. ♦

Assim pelo teorema 23 daqui em diante trabalharemos somente em ℝ.

Produto Interno - Um Produto Interno é uma operação que associa a cada par de vetores u, v ∈ ℝⁿ um número real ⟨u,v⟩, que satisfaça as seguinte condições (axiomas):

⟨u,v⟩ = ⟨v,u⟩.
⟨Cu,v⟩ = C⟨u,v⟩ (∀C ∈ ℝ).
⟨u,v + w⟩ = ⟨u,v⟩ + ⟨u,w⟩.
⟨u,u⟩ = 0 ⇔ u = 0.

O Produto Interno canônico em ℝⁿ é o produto escalar:

⟨u,v ⟩ = uTv

(7)

Em particular se v é um vetor em um espaço vetorial V munido de um produto interno, o comprimento desse vetor, também chamado de norma, é definido por:

∘ ------ ||v|| = ⟨v, v⟩.

(8)

Exercício 24. Deduza a partir de (1)—(4) acima as seguintes igualdades

⟨u,Cv⟩ = C⟨u,v⟩ (∀C ∈ ℝ).
⟨u + v,w⟩ = ⟨u,w⟩ + ⟨v,w⟩.
⟨u,0⟩ = ⟨0,v⟩ = 0.

Exercício 25. Mostre que se Θ é o ângulo entre vetores u,v, então:

⟨u,v⟩ = ||u||||v ||cosΘ.

(9)

Se ⟨u,v⟩ = 0 então dizemos que u e v são ortogonais, para quaisquer u e v diferentes de 0. Para u e v ortogonais escrevemos u ⊥ v.

Teorema 26. Se A é uma matriz simétrica então autovetores associados a autovalores distintos de A são ortogonais.

Demonstração. Sejam λ₁ e λ₂ autovalores distintos com respectivos autovetores u e v. Vamos mostrar ⟨u,v⟩ = u^Tv = 0.

T T T T T T λ1u v = (λ1u )v = (Au ) v = u Av = u λ2v = λ2u v.

Logo, temos (λ₁ - λ₂)u^Tv = 0, como λ₁ - λ₂≠0, pois são diferentes, temos u^Tv = 0, portanto u ⊥ v. ♦

Lema 27 (Desigualdade de Cauchy-Schwarz). Se u e v são dois vetores quaisquer em um espaço vetorial real V, munido de Produto Interno então:

⟨u,v ⟩2 ≤ ||u ||2||v||2

(10)

Esboço de uma prova. Sejam u e v l.i., pois se fossem linearmente dependentes vale a igualdade na equação acima. Para todo x ∈ ℝ temos:

2 2 ||xu + v|| = x ⟨u,u⟩+ 2x⟨u,v⟩+ ⟨v, v⟩ > 0.

Portanto o discriminante 2⟨u,v⟩)² - 4(⟨u,u⟩)(⟨v,v⟩é < 0, donde segue a desigualdade. ♦

Exemplo 28 (Aplicação da desigualdade de Cauchy-Schwarz). Seja G um grafo sobre V = {1,2,…,n}. Suponha que G não contém triângulos. Logo para vértices i e j que formam uma aresta temos d(i) + d(j) < n. Assim

∑ ∑ n|E (G)| > (d(i)+ d(j)) = d(i)2. ij∈E((G) i

Pondo d = (d(1),d(2),…,d(n))^T temos pela Desigualdade de Cauchy-Schwarz que ||d||²||1||² ≥⟨d,1⟩², onde 1 = (1,1,…,1)^T. Portanto,

( )2 ∑ 2 2 --1-- 2 1- ∑ 1- 2 n|E(G )| > d(i) = ||d|| ≥ ||1||2⟨d,1⟩ = n d(i) = n (2|E(G )|) , i i

onde a última igualdade segue da soma dos graus ser duas vezes o número de arestas. Tomando os extremos da desigualdade concluímos que para um grafo G com n vértices e sem triângulos temos

2 |E(G )| ≤ n-. 4

Corolário 3 (Desigualdade Triangular). Segue da desigualdade de Cauchy-Schwarz que

||u + v|| ≤ ||u ||+ ||v ||.

(11)

♦

Dados dois vetores u e v, vamos denotar a projeção ortogonal de v sobre u por v^′. Como v^′ é um múltiplo escalar do vetor u temos

′ u v = α---- ||u ||

(12)

para algum α ∈ ℝ.

Para determinar α:

′ -v-- = cosθ = -⟨u,v-⟩-, ||v || ||u ||||v||

logo

α = ||v′|| = ⟨u,-v⟩-∴ v′ = ⟨u,-v⟩u. ||u|| ⟨u, u⟩

A partir de uma base qualquer {u₁,u₂,…,u_n} do ℝⁿ podemos obter, através de projeções ortogonais, uma base ortogonal {v₁,v₂,…,v_n} da seguinte maneira

v1 = u1 ⟨u1,-u2⟩- v2 = ⟨u1, u1⟩u1 ⟨u ,u ⟩ ⟨u ,u ⟩ v3 = u3 - ---1--3-u1 - --2--3-u2 ⟨u1,u1 ⟩ ⟨u2, u2⟩ .. .. . = . vn = un - ⟨u1,-un⟩u1 - ⟨u2,un⟩u2 - ⋅⋅⋅- -⟨un--1,un⟩-un- 1 ⟨u1, u1⟩ ⟨u2,u2⟩ ⟨un -1,un-1⟩

que é conhecido como Processo de Ortogonalização de Gram-Schmidt. Ainda, podemos normalizar os vetores v_i’s de modo a formarmos uma base ortonormal.

Uma matriz é dita ortogonal se suas colunas formam um conjunto de vetores ortonormais no ℝⁿ. Equivalentemente, Q^TQ = Id, pois se Q = (q₁,…,q_n) temos:

( ) q1T ( ) | q2T| 1 0 || . || (q1,...,qn) = |( ... |) , ( .. ) 0 1 qnT

pois

qiTqi = ⟨qi,qi⟩ = 1eqiTqj = ⟨qi,qj ⟩ = 0.

Observação 29. Q^T = Q^-1

Exercício 30. Mostre que

||Qv|| = ||v||.
⟨Qu,Qv⟩ = ⟨u,v⟩.
Produto de matrizes ortogonais é uma matriz ortogonal.

Observação 31. Matriz ortogonal tem somente autovalores {+1,-1}.

Teorema 32 (Teorema espectral real). Se A é uma matriz simétrica então existe uma base ortonormal do ℝⁿ formada por autovetores de A.

Demonstração. Este teorema será demonstrado adiante, no teorema equivalente 33. Mostre que esses teoremas são equivalentes. ♦

Teorema 33. Se A é uma matriz simétrica então existe Q ortogonal tal que Q^TAQ = diag(λ₁,λ₂,…,λ_n), onde λ₁,λ₂,…,λ_n são os autovalores de A.

Demonstração. A prova é por indução na dimensão da matriz A. O caso n = 1 é exercício.

Sejam λ₁,λ₂,…,λ_k autovalores distintos de A e u₁,u₂,…,u_k autovetores linearmente independentes associados aos autovalores. Completamos {u₁,u₂,…,u_k} para uma base {u₁,u₂,…,u_k,u_k+1,…,u_n} do ℝⁿ.

Usando Gram-Schmidt, podemos tomar uma base ortonormal

{v1,v2,...,vk,vk+1,...,vn}.

Observamos que v₁ é um autovetor de A. Agora tomemos Q₁ como a matriz

Q1 = (v1,...,vn)

e seja B tal que seja igual a:

T B = Q(1AQ1) v1T | v2T| = || . || A (v1,v2,...,vn ) ( .. ) vnT ( v T) | 1T| = || v2 || (Av ,Av ,...,Av ) ( ... ) 1 2 n vnT ( T) v1 || v2T|| = |( .. |) (λ1v1,Av2, ...,Avn) .T ( vn ) λ1v1Tv1 v1TAv2 ... v1TAvn | λ1v2Tv1 | = || . || ( .. A1 ) λ1vnTv1 ( λ 0 ... 0) | 1 | = || 0 || . ( ... A1 ) 0

Como B é simétrica, pois B^T = (Q₁^TAQ₁)^T = Q₁^TAQ₁, temos que A₁ é simétrica e, portanto, existe Q₂ ortogonal tal que Q₂^TA₁Q₂ = diag(μ₁,μ₂,…,μ_n-1) com μ_i autovalor de A₁ para todo i.

Tomemos então Q₃

( ) |λ1 0 ... 0| Q = | 0 | , 3 |( ... Q2 |) 0

e, finalmente, Q = Q₁Q₃. Claramente, Q₃ é ortogonal e Q é ortogonal, pois é produto de matrizes ortogonais.

Agora,

T T T T Q AQ = (Q(1Q3 )A (Q1Q3) ) =( Q1Q 3AQ1Q3 ) ( ) 1 0 ... 0 λ1 0 ... 0 1 0 ... 0 | 0 | | 0 | | 0 | = || .. T || || .. || || .. || ( . Q 2 ) ( . A1 ) ( . Q2 ) 0 0 0 ( λ 0 ... 0) ( 1 0 ... 0) | 1 | | | = || 0. || || 0. || ( .. QT2A1 ) ( .. Q2 ) 0 0 ( ) λ1 0 ... 0 || 0 || = |( .. T |) . Q2A1Q2 ( 0 ) λ1 0 ... 0 | 0 | = || . || . ( .. diag(μ1,...,μn-1) ) 0

Agora somente falta provar que μ₁,…,μ_n-1 são autovalores de A₁.

Exercício 34. Se A = ( )
D B
0 C com D e C matrizes quadradas, então p_A(x) = p_D(x)p_C(x). Conclua que os autovalores de C são autovalores de A.

♦

Exercício 35. Provar que o Teorema 32 e Teorema 33 são equivalentes.

Corolário 4 (Decomposição Espectral de Matrizes Simétricas). Se A é simétrica e {v₁,v₂,…,v_n} uma base ortonormal de autovetores, então

A = λ1v1vT + ⋅⋅⋅+ λnvnvT 1 n

(13)

8 Teorema de Courant-Fischer e Teorema de Perron-Frobenius

Proposição 36. Seja A uma matriz simétrica e λ₁ ≥ λ₂ ≥ … ≥ λ_n os autovalores de A. Então

λ1 = m||xa|x|=1⟨Ax, x⟩.

Demonstração. Por definição ⟨Ax,x⟩ = x^TAx. Pelo Teorema 33, podemos escrever A = QDQ^T. Portanto x^TAx = x^TQDQx = (Q^Tx)^TD(Q^Tx) e fazendo y = Q^Tx temos:

( ) ( y ) λ1 0 | 1| yTDy = (y ,y ,...,y )|( .. |) || y2|| 1 2 n . ( ... ) 0 λn yn ( ) y1 || y2|| = (λ1y1,λ2y2,...,λnyn)|( ..|) . yn = λ1y21 + λ2y22 + ...+ λny2n 2 2 2 ≤ λ1(y1 + y2 + ...+ yn) = λ1,

pois temos λ₁ ≥ λ₂ ≥… ≥ λ_n e ||y|| = 1 (exercício 30). ♦

Exercício 37. Mostrar que o máximo de ⟨Ax,x⟩ é atingido se e só se x for autovetor de A de norma 1.

Seguindo a proposição anterior, temos o seguinte para o segundo maior autovalor de uma matriz simétrica.

Proposição 38. Seja A matriz simétrica, λ₁ ≥ λ₂ ≥ … ≥ λ_n autovalores de A com respectivos autovetores ortonormais q₁,q₂,…,q_n. Então

λ2 = m||axx||=1⟨Ax,x ⟩ x⊥q1

Demonstração. Partindo do princípio análogo ao da proposição anterior tomamos y = Q^Tx. De ||x|| = 1 temos ||y|| = 1 e, também do exercício 30, de temos que ⟨Q^Tx,Q^Tq₁⟩ = ⟨x,q₁⟩ = 0, ou seja, y ⊥ Q^Tx. Ainda,

( ) 0 ||⟨q2,x ⟩|| QTx = | .. | || . || (⟨qn,x ⟩)

Após a resolução análoga à proposição anterior, obtemos ao invés de λ₁y₁² + λ₂y₂² + … + λ_ny_n² a expressão 0 + λ₂y₂² + λ₃y₃² + … + λ_ny_n² e como λ₂ é o maior autovalor que aparece na expressão podemos afirmar

m||axx||=1⟨Ax, x⟩ = m||ayx||=1 ⟨Dy, y⟩ ≤ λ2. x⊥q1 y⊥QTq1

♦

Baseado nas proposições anteriores podemos demonstrar que

λi = max ⟨Ax,x ⟩. ||x||=1 x⊥qj(1≤j<i)

Vamos mostrar um resultado mais geral.

Teorema 39 (Teorema de Courant-Fischer). Seja A uma matriz simétrica com autovalores λ₁ ≥ λ₂ ≥ ⋅⋅⋅ ≥ λ_n. Então

λk = max min ⟨Ax,-x⟩, dimUU=kxx∈⁄=U0 ⟨x,x⟩

onde U varia sobre todo subespaço do ℝⁿ de dimensão k.

Demonstração. Seja U um subespaço qualquer de dimensão dim = k e q₁,…,q_n autovetores ortonormais associados a λ₁,λ₂,…,λ_n, respectivamente.

Tomamos os subespaços V _k = [q₁,…,q_k], e T_k = [q_k+1,…,q_n] e, como dimU = k temos que existe x ∈ u∩T_k-1≠{0} pois dimT_k-1+dimU = n+1.

Como x ∈ T_k-1 podemos escrever x como a combinação linear

∑n x = αiqi. i=k

Seja Q = (q₁,…,q_n) a matriz ortogonal de autovetores e façamos y = Q^Tx. Como Q preserva produto interno (exerc. 30) e

( ) 0 ( ) ( ) || ... || y1 | ⟨q1,x ⟩| || 0 || || y2|| QTx = | ⟨q2,x ⟩| = || α || = y = | .. | |( ... |) || .k|| || . || ⟨q ,x ⟩ || .. || (yn ) n ( αn )

temos que

∑n ∑n ∑n ⟨Ax,x-⟩ ⟨Dy,-y-⟩ -∑i=1λiy2i- -∑i=kλiα2i λk∑---i=k-α2i- ⟨x, x⟩ = ⟨y, y⟩ = ni=1 y2i = ni=kα2i ≤ ni=kα2i = λk.

Agora, para U = V _k temos, de modo análogo, que x = ∑ _i=1^kα_iq_i e

⟨Ax, x⟩ ⟨Dy, y ⟩ ∑ki=1 λiα2i ⟨x,x-⟩-= ⟨y,y-⟩-= -∑k----2--≥ λk. i=1 αi

Logo,

⟨Ax, x⟩ λk = max min -------. dimUU=k xx∈⁄=U0 ⟨x,x⟩

♦

Exercício 40 (Teorema de Courant-Fischer). Mostre que também vale o seguinte

λk = min max ⟨Ax,-x-⟩, dimU=Un -k+1 x∈xU⁄=0 ⟨x,x ⟩

onde U subespaço de dimensão n - k + 1 no ℝⁿ.

Proposição 41 (Teorema do Entrelaçamento). Seja A = (a_i,j) matriz simétrica com autovalores λ₁ ≥ λ₂ ≥ … ≥ λ_n e A_k = (a_i,j)_i,j≠k matriz (n - 1) × (n - 1) simétrica, com autovalores μ₁ ≥ μ₂ ≥… ≥ μ_n-1. Então

λ1 ≥ μ1 ≥ λ2 ≥ μ2 ≥ ...≥ λn-1 ≥ μn- 1 ≥ λn.

Demonstração. Vamos mostrar que λ_j ≥ μ_j ≥ λ_j+1 para A₁. Seja U subespaço no ℝ^n-1 de dimensão dimU = j tal que

⟨A1x,x⟩ μj = mxi∈nU -⟨x,x⟩-- x⁄=0

e seja {u₁,u₂,…,u_n} uma base de U. Definimos

( ) ′ 0 ui = ( ui) (∀i = 1,2,...,j)

sendo U′ o subespaço [u₁′,u₂′,…,u_j′] no Rⁿ de dimensão dimU = j

μ = min ⟨A1x,-x⟩ =* min ⟨Ax,-x⟩ ≤ max min ⟨Ax,-x⟩-= λ . j x∈U ⟨x, x⟩ x∈U′ ⟨x,x⟩ U x∈U ⟨x,x ⟩ j x⁄=0 x⁄=0 dim U=j x⁄=0

* Pois ao multiplicar, anula-se a linha 1 e a coluna 1 da matriz A, resultando na matriz A₁.

Para mostrar μ_j ≥ λ_j+1 para A₁ usamos o exercício 40. Os detalhes ficam como exercício. ♦

Seja a matriz A = (a_ij) e, dada uma permutação ρ de 12…n denotamos por A_ρ a matriz (a_ρ(i)ρ(j)).

Exemplo 42. Suponha a permutação 3214567, ou seja, ρ(1) = 3,ρ(3) = 1,ρ(i) = i(∀_i≠1,3) e considere a matriz

( ) 2 0 0 1 3 || 4 2 1 5 5|| A = || 1 2 7 3 0|| . || 6 0 0 2 1|| ( 1 0 0 7 2)

A matriz A_ρ é

( 7 2 1 3 0) | 1 2 4 5 5| || || Aρ = || 0 0 2 1 3|| . | 0 0 6 2 1| ( 0 0 1 7 2)

Exercício 43. Seja P a matriz obtida da matriz identidade permutando-se as linhas de Id de acordo com ρ. Mostre que

A_ρ = PAP^T;
A_ρ tem os mesmos autovalores de A;
se v é um autovetor de A então v_ρ = Pv é um autovetor de A_ρ.

Dizemos que a matriz A é irredutível se não existe permutação ρ tal que

( B C ) ( ) Aρ = 0 D

com B e D matrizes quadradas.

Teorema 44 (Teorema de Perron-Frobenius). Seja A, simétrica, não-negativa (a_ij ≥ 0), irredutível e com autovalores λ₁ ≥ λ₂ ≥… ≥ λ_n. Então

λ₁ > 0 e existe autovetor não-negativo associado v₁;
λ₁ > λ₂;
|λ_i|≤ λ₁ para todo i = 2,…,n;
λ₁ = -λ_n se, e só se, existe ρ tal que A_ρ = .

Demonstração. (1): De A não negativa tr(A) = ∑ _ia_i,i ≥ 0. Pelo exercício 10 e Teorema 33 tr(A) = ∑ _iλ_i, logo λ₁ ≥ 0.

Seja u autovetor com norma 1 associado a λ₁. Assim,

∑n ∑n ∑n ∑n λ1 = uTAu = aijuiuj ≤ aij|ui||uj| ≤ λ1. i=1 j=1 i=1j=1

logo v =

( )
|u1|
|| |u2|||
| .. |
|| . ||
( |un|)

é um autovetor (exercício 37) associado a λ₁ não-negativo e tem norma 1.

Suponha que existam i’s tais que u_i = 0. Seja ρ uma permutação tal que |U_i| > 0 para todo i ≤ m e |u_i| = 0 pra todo i > m. Escrevendo A_ρ = ( B C )
( )
D E e (v₁)_ρ = ( u ′)
( )
0 temos então

( B C ) (λ u ′) ( ) ( 1 ) D E = 0

Logo D = 0 e portanto, A_ρ = ( )
B C
( 0 E )

, ou seja A é uma matriz redutível, absurdo. Com isso, v₁ > 0.

Agora vamos mostrar que λ₁≠0. Supondo λ₁ = 0 temos

( ) ( ) B C 0 (D E ) = λ1 ( 0)

(14)

que, analogamente, contraria o fato de A ser irredutível.

(2): Vamos mostrar que λ₁ > λ₂.

Como λ₁ > λ₂, pelo Teorema 21 ma(λ₁) = mg(λ₁) pois A matriz simétrica.

Suponha mg(λ₂) ≥ 2 e sejam u,v autovetores ortonormais de λ₁. Definimos o vetor

( u + |u |) | 1 1 | u′ = || u2 +.|u2||| ( .. ) un + |un|

autovetor de λ₁. Claramente, u_i + |u_i|≥ 0(∀i) e, portanto, u_i + |u_i| > 0(∀i), caso contrário a matriz não seria irredutível, como vimos acima (equação 14).

Idem para

( v1 + |v1|) ′ | . | v = ( .. ) . vn + |vn|

Por hipótese, u^Tv = 0 e, dessa forma, no podemos ter u_iv_i > 0 para todo i. Absurdo. Assim, mg(λ₁) = 1 e λ₁ > λ₂.

(3): |λ |
i ≤ λ_i(∀i). Se v_i autovetor unitário de λ_i então

||n n || n n || T || |∑ ∑ | ∑ ∑ |λi| = v iAvi = || ak,lvkvl|| ≤ ak,l|vk||vl| ≤ λ1 k=1 l=1 k=1 l=1

pois v₁ é autovetor unitário.

(4): Sejam λ autovalor com autovetor v e ρ tal que A_ρ = ( 0 B )
( T )
B 0 .

Escrevemos v_ρ = ( )
v′
( v′′) . Logo A_ρv_ρ = λv_ρ. Isso implica que

( ) ( ′) ( ′) ( ) ( ′) ( 0T B ) ( v ′′) ( v′′) Bv ′′ ( λv′′) B 0 v = λ v ⇔ BTv ′ = λv ⇔

( ) ( ) ( ) ( ) ( ′′) - λv ′ 0 B v ′ v′ - BvT ′ = ( λv ′′ ) ⇔ ( BT 0 ) ( - v′′) ⇔ λ ( - v ′′) B v

ou seja, -λ autovalor de A_ρ e ( v′)
( ′′)
- v

autovetor associado. Portanto -λ é autovalor de A.

Agora nos resta provar a recíproca. Se -λ₁ é autovalor então seja v um autovetor unitário de -λ₁.

||n n || n n || T || ||∑ ∑ || ∑ ∑ λ1 = |- λ1| = v Av = || ai,jvivj|| ≤ ai,j |vi||vj| ≤ λ1. i=1 j=1 i=1j=1

Dessa forma, u = ( )
|v1|
|| |v2|||
|| .. ||
| . |
( |vn|)

autovetor de λ₁ (com |vi|

≠0).

Seja ρ uma permutação tal que v_ρ = ( )
vρ(1)
| vρ(2)|
|| .. ||
|| . ||
( vρ(n)) com v_ρ(i) > 0 para todo i ≤ m e v_ρ(i) < 0 para todo i > m e escrevemos

( ′ ) v ′′ vρ = ( - v )

com v^′,v^′′ > 0 e escrevemos

( ) B C A ρ = ( D E ) .

Dessa forma ( )
B C
( D E )

= λ₁

⇒

= -λ₁

⇒

ou seja,

{ Bv ′ + Cv ′′ = λ1v′ Bv ′ - Cv ′′ = - λ v ′ 1

e como a matriz é não negativa e o vetor positivo temos que B = 0. Analogamente, de

{ ′ ′′ ′′ Dv + Ev = λ1v Dv ′ - Ev′′ = λ1v ′

temos que E = 0 ∴ A_ρ = ( )
0 C
( D 0)

Exercício 45. Concluir que D = C^T

♦

Exercício 46. Mostre que se A = ( )
0 B
( BT 0) então λ_i = λ_n-i+1

9 Teoria Espectral de Grafos

Seja G um grafo com V (G) = {1,2,…,n}. Definimos a matriz de adjacências A do grafo G como A(G) = (a_ij), onde

( { 1, se ij ∈ E (G) aij = 0, se ij ∕∈ E (G) (

Definimos, ainda, o espectro Sp(G) = (λ₁,λ₂,…,λ_n) do grafo G, com λ₁ ≥ λ₂ ≥ ⋅⋅⋅ ≥ λ_n os autovalores reais de A.

Exemplo 47 (Grafo completo Kⁿ). O polinômio característico p_A(x) de um grafo completo com n vértices é igual a

n-1 pA(Kn )(x ) = (A - xId) = (x- (n - 1))(x + 1) ,

e o seu espectro é da forma

n Sp(K ) = (n - 1,- 1,- 1,...,- 1).

Exemplo 48 (Grafo bipartido completo K_r,r). O polinômio característico de um grafo bipartido completo com classes de tamanho r é

pA(Kr,r)(x ) = x2n-2(x + r)(x - r).

Exemplo 49 (Grafo de Petersen). O Grafo de Petersen, cujo diagrama é dado na figura abaixo, tem polinômio característico

p (x) = (x - 3)(x+ 2)4(x - 1)5. A

Observação 50. Dois grafos distintos podem ter o mesmo polinômio característico como mostra o seguinte exemplo

Exemplo 51.

Os grafos da figura ?? têm polinômio característico

3 5 pA(a)(x) = PA(b)(x ) = 4x - x .

Proposição 52. O elemento d_ij da matriz A^k é o número de seqüências (i,x₁,x₂,…,x_k-1,j) com vértices consecutivos adjacentes, conhecidos como passeios de comprimento k (k é o número de arestas no passeio).

Demonstração. Temos que

∑n ∑n ∑n dij = ⋅⋅⋅ aix1ax1x2ax2x3 ...axk-2xk-1axk-1j x1=1 x2=1 xk-1=1

Assim, para as seqüências de vértices (i,x₁,x₂,…,x_k-1,j) adjacentes, o termo referente da soma é igual a 1. Se dois vértices na seqüência não são adjacentes, então o termo da soma é igual a 0, pois o elemento referente da matriz de adjacências é 0. Portanto, o elemento d_ij da matriz A^k é igual ao número de seqüências de vértices consecutivos adjacentes, ou seja, o número de passeios com k arestas de i até j. ♦

Exemplo 53 (k = 4). Nesse caso,

∑n ∑n ∑n dij = aimamlalkakj m=1 l=1 k=1

Na diagonal, d_ii é o número de passeios (i,l,m,k,i). Assim, d_ii conta duas vezes as seqüências que formam circuitos de tamanho quatro (i,a,b,c,i), i,a,b,c dois-a-dois distintos, mais as seqüências da forma (i,j,i,j,i), mais as seqüências da forma (i,a,b,a,i), b≠i, mais as seqüências da forma (i,a,i,b,i), a≠b.

Exemplo 54 (k = 3). Assim,

∑n ∑n dij = aimamlalj. m=1 l=1

Os elementos da diagonal contam as seqüências (i,a,b,i). Assim, d_ii é igual a duas vezes o número de triângulos que contém o vértice i, logo

n tr(A3) = ∑ d = 6t, ii i=1

onde t é o número de triângulos do grafo.

Observação 55. Do Teorema espectral

A = QTDQ

logo

2 T T T 2 A = Q DQQ DQ = Q D Q

Como A ~ B implica que tr(A) = tr(B) temos tr(A²) = tr(D²) = ∑ _i=1ⁿλ_i².

Genericamente,

n k T k k ∑ k A = Q A Q e tr(A ) = λ i. i=1

Assim,

∑n tr(A ) = λi = 0, i=1

n tr(A2) = ∑ λ 2 = 2|E |, i i=1

n tr(A3) = ∑ λ 3 = 6t, i i=1

onde t é o número de triângulos no grafo.

Exercício 56. Mostre que ∑ _i=1ⁿλ_i^k é inteiro para todo k ∈ ℕ.

Exercício 57. Mostre que grafos isomorfos têm matrizes de adjacência semelhantes.

9.1 Grau

Teorema 58. Seja G um grafo e λ₁o maior autovalor de A(G), então d(G) ≤ λ₁ ≤ Δ(G).

Demonstração.

(1) | | 1 ||1.|| λ1 = max xTAx ≥ uTAu, onde u = √---|| ..|| . ||x||=1 n (1)

Logo,

( ) T ( ) ( ) T ( ) 1 1 1 d1 || 1|| || 1|| || 1|| || d2|| ∑n λ1 ≥ 1-|| ...|| A || ...|| = 1|| ...|| || ... || = 1- di = d(G ). n |( |) |( |) n|( |) |( |) n i=1 1 1 1 dn

Por outro lado, tome

( ) | v1| | v2| v1 = |( ...|) > 0 v n

autovetor positivo a λ₁ e seja v_k = max_iv_i. Então,

∑n ∑n λ1vk = akivi ≤ akivk = dkvk ≤ Δ (G)vk i=1 i=1

logo, λ₁ ≤ Δ(G). ♦

Corolário 5. Para todo i ∈{1,2,…,n}

|λi| ≤ Δ (G).

Demonstração. Imediato do Teorema de Perron-Frobenius. ♦

Corolário 6. Se G é k-regular, então λ₁(G) = k.

Demonstração. Como G é k-regular, então d(G) = k e Δ(G) = k. Pelo Teorema 58, temos

k = d(G ) ≤ λ1 ≤ Δ (G ) = k.

Logo, λ₁ = k. ♦

Corolário 7. Se λ₁ = d(G), então G é λ₁-regular.

Demonstração. Temos que λ₁ = d(G). Logo,

( 1) T | 1| λ1 = 1-A1-, onde 1 = || .|| , 1T1 ( ..) 1

pois

∑n 1T1 = n e 1TA1 = di. i=1

Então, 1 é autovetor associado à λ₁. Logo,

( ) ( ) |d1 | | λ1| |d2 | | λ1| A1 = λ11 ⇔ |( ... |) = |( ...|) . d λ n 1

ou seja, G é λ₁-regular. ♦

9.2 Subgrafos

Teorema 59. Se Sp(G) = (λ₁,λ₂,…,λ_n) e Sp(G - v) = (μ₁,μ₂,…,μ_n-1), então

λ1 ≥ μ1 ≥ λ2 ≥ μ2 ≥ ⋅⋅⋅ ≥ λn-1 ≥ μn- 1 ≥ λn.

Demonstração. Imediato do Teorema do Entrelaçamento. ♦

Exercício 60. O que pode ser dito a respeito do espectro de G - v - u?

Teorema 61. Se H ⊆ G, então λ₁(H) ≤ λ₁(G).

Demonstração. Seja B a matriz de adjacências de H = (V (G),E(H)), então λ₁(H) = v₁^TBv₁, com v₁ = ( )
v1
|| v2||
| ..|
( .)
vn autovetor unitário e positivo. Então,

T ∑ ∑ ∑ ∑ T λ1(H) = v1 Bv1 = bijvivj ≤ aijvivj ≤ v1 Av1 ≤ λ1(G). i j i j

Portanto, λ₁(H) ≤ λ₁(G). ♦

Exercício 62. Descubra um exemplo com H ⊆ G e tal que λ₂(H) > λ₂(G).

9.3 Conexidade

Proposição 63. Seja G um grafo com componentes conexas C₁,C₂,…,C_m, então existe uma permutação σ de 1,2,…,n tal que

( ) | A11 0 ... 0 | | 0 A22 ... 0 | A σ = || ... ... ... ... || , |( 0 0 ... A |) mm

onde A_ii é matriz de adjacência da componente conexa C_i.

Exercício 64. Prova da Proposição 63.

Exercício 65. Se G é desconexo então a matriz A(G) é redutível.

Teorema 66. Se G é um grafo conexo, então λ₁ > λ₂.

Demonstração. Como G é conexo, a matriz de adjacências A(G) é irredutível. Portanto, pelo Teorema de Perron-Frobenius, λ₁ > λ₂. ♦

Observação 67. Se um grafo G tem λ₁ > λ₂, G não é necessariamente conexo, como mostra o seguinte exemplo

Exemplo 68. O grafo da figura ?? tem espectro Sp = (3,2,-1,-1,-1,-1,-1) e é desconexo.

Teorema 69. Se G é um grafo k-regular então ma(λ₁) é o número de componentes conexas de G.

Demonstração. Pelo corolário 6, λ₁ = k. Seja

( ) | v1| v = | v2| 1 |( ...|) v n

autovetor associado a λ₁, então

∑n λ1v1 = Av1 ⇒ kvi = aijvj. j=1

Suponha, sem perda de generalidade, que

v = max v . 1 1≤j≤n j

Então,

∑n ∑n kv1 = a1jvj ≤ a1jv1 = kv1. j=1 j=1

Logo,

∑n ∑n a1jvj = a1jv1. j=1 j=1

Portanto, v₁ máximo implica que v_j = v₁ para todo j ∈ N(1) = {x ∈ V : {x,1}∈ E}.

Notemos que para ℓ ∈ N(1)

∑n ∑n kvℓ = aℓjvj ≤ aℓjvℓ = kvℓ, j=1 j=1

e da mesma forma,

vj = vℓ ∀j ∈ N (ℓ).

Indutivamente, v_j = v_ℓ para todo vértice ℓ pertencente a mesma componente conexa que 1.

Agora, seja

vt = 1m≤ajx≤n vj, vj⁄=v1

e C(1) a componente conexa que contem o vértice 1. Então

∑n ∑ ∑ ∑ ∑ kvt = atjvj = atjvj+ atjvj = atjvj ≤ atjvt ≤ kvt. j=1 j∈C(1) j∕∈C (1) j∕∈C(1) j∕∈C(1)

Logo, v_j = v_t para todo j ∈ N(t). Como antes, temos v_j = v_t para todo j ∈ C(t), onde C(t) é a componente conexa que contém o vértice t.

Repetindo esse argumento temos que v₁ é constante em cada componente conexa de G. Logo, dimV _λ₁ = mg(λ₁) = m = ma(λ₁). ♦

9.4 Grafos bipartidos

Exercício 70. Usando a técnica da demonstração do último teorema mostre que se G é conexo, k-regular e λ₁ = -λ_n então G é bipartido.(Dica: sinal(v_j) = sinal(N(v_j)) = sinal(N(N(v_j))) = ….)

Exercício 71. Mostre que se G é bipartido então existe permutação σ tal que

( ) Aσ = 0 B BT 0

onde B é uma matriz quadrada.

Exercício 72. Mostre que se G = (A ∪ B,E) é bipartido e

Δx = max {d(v) : v ∈ x}

para x ∈{A,B}, então λ₁ ≤ √-------
ΔA ΔB

Exercício 73. Mostre que se G é uma floresta então

√ ------√ ----- λ1 ≤ min{2 Δ - 1, n - 1}.

(Dica: λ₁ = -λ_n e tr(A²) ≤ 2n - 2.)

Teorema 74. Se G é conexo, são equivalentes

λ₁ = -λ_n;
λ_i = -λ_n+1-i (∀i);
G é bipartido.

Demonstração. Exercício 71 e Perron-Frobenius. ♦

10 α,χ,ω,λ

Relembrando algumas definições temos
α(G) — tamanho de um conjunto independente máximo;
χ(G) — número cromático (número mínimo de partes independentes em V (G));
ω(G) — clique máximo (número de vértices do maior subgrafo completo). Esses números satisfazem as seguintes desigualdades

χ (G )α(G ) ≥ |V | χ(G ) ≥ ω(G ) χ(G ) ≤ Δ (G )+ 1.

Exercício 75. Mostre que ω(G) ≤ λ₁(G) + 1, onde λ₁(G) é o maior autovalor de A(G).

Teorema 76. Se Sp(G) = (λ₁,λ₂,…,λ_n) então

1 - λ1-≤ χ (G ) ≤ 1+ λ λn 1

Demonstração. Primeiro, vamo mostrar que χ(G) ≤ 1 + λ₁. Suponha que temos λ₁ + 1 cores disponíveis. Seja

(v ) | 1.| v = ( ..) > 0 vn

um autovetor positivo associado a λ₁. Tome σ uma permutação tal que

( ) ( ) vσ(1) u1 | .. | | ..| vσ = ( . ) = ( .) vσ(n) un

e u₁ ≥ u₂ ≥… ≥ u_n.

Para qualquer vértice i definimos o conjunto X = X(i) = {j ∈ V : ij ∈ E e j < i} e temos que X ≤ λ₁ pois

∑ ∑ ∑ ∑ λ1vσ(i) = aσ(i)σ(j)vσ(j) = vσ(j) ≥ vσ(j) ≥ vσ(i) = |X |vσ(i) j j∈N(i) j∈N(i) j∈N (i) j<i j<i

ou seja

|X | ≤ λ1.

Assim, nos vértices de X usamos no máximo λ₁ cores, logo há cor disponível para pintar o vértice i sem que vértices adjacentes tenham a mesma cor.

Agora vamos provar a outra desigualdade do teorema

λ1 1- λ--≤ χ(G ). n

Suponha χ(G) = m e escreva V (G) = V ₁∪V ₂∪

∪V _m com E(G[V _i]) = 0. Existe uma permutação σ tal que

( ) A11 A12 ⋅⋅⋅ A1m || ... ... ... ... || A σ = |( Am1 Am2 ⋅⋅⋅ Amm |)

com A_ii = 0, quadrada (∀i ∈{1,…,m}) e, quando i≠j, com A_ij = A(G[V _i∪ V _j]).

O resultado seguirá das seguintes afirmações cujas provas serão adiadas.

Afirmação 77. Para a matriz simétrica e não-negativa

(A A ) An ×n = A 11 A 12 21 22

com A_ii quadrada vale que

λ1(A) + λn(A) ≤ λ1(A11)+ λ1(A22 )

onde λ₁ e λ_n são o maior e menor autovalor das matrizes, respectivamente.

Afirmação 78. Para a matriz simétrica e não-negativa

( A A ⋅⋅⋅ A ) | 1.1 1.2 . 1.m | A = || .. .. .. .. || (Am1 Am2 ⋅⋅⋅ Amm )

temos

m∑ λ1(A )+ (m - 1)λn (A ) ≤ λ1(Aii). i=1

Pela Afirmação 78 em A_σ temos

λ1(Aσ )+ (m - 1)λn(A σ) ≤ 0

como λ_i(A_σ) = λ_i(A) e λ_n(A) < 0 segue que

(m - 1) ≥ --λ1 ⇒ m ≥ 1- λ1- λn λn

e portanto χ(G) ≥ 1 - λ₁∕λ_n. ♦

Agora, resta demonstrar os fatos usados na prova do teorema.

Prova da Afirmação 77. Escrevemos

( ) ( ) ( ) A = A11 A12 = 0 A12 + A11 0 = B + C A12T A22 A12T 0 0 A22

e dessa forma o maior autovalor de A é dado por

T ( T T ) λ1 (A ) = |m|ua|x|=1u Au = |m|ua|x|=1 u Bu + u Cu T T ≤ |m|ua|x|=1u Bu + |m|ua|x|=1 u Cu = λ1 (B )+ λ1 (C ),

pelo exercício 34, página 55, temos que λ₁(C) = max{λ₁(A₁₁),λ₁(A₂₂)}. Vamos supor, sem perda de generalidade, que λ₁(C) = λ₁(A₁₁). Agora, para o menor autovalor temos

T ( T T ) λn(A) = m||iun||=1u Au = ||mui||n=1 u Bu + u Cu ( T ) ≤ m||iun||=1 u Bu + λ1(A22) = λmin(B )+ λ1 (A22 )

onde λ_min(B) é o menor autovalor da matriz B. Pelo item (4) do Teorema de Perron-Frobenius (teorema 44, página 66) sabemos que λ_min(B) = -λ₁(B).

Portanto, λ₁(A) + λ_n(A) ≤ λ₁(A₁₁) + λ₁(A₂₂). ♦

Prova da Afirmação 78. Vamos provar por indução em m. O caso m = 2 segue da Afirmação 77. Por hipótese indutiva em

( ) A1,1 A1,2 ⋅⋅⋅ A1,m-1 | .. .. .. .. | A′ = || . . . . || ( Am -1,1 Am -1,2 ⋅⋅⋅ Am -1,m- 1)

temos

m∑-1 λ1(A′)+ (m - 2)λmin(A′) ≤ λ1 (Aii). i=1

(15)

Pela Afirmação 77 em

( ) | A1,m | | A′ ... | A = || . || ( .. ) Am,1 ⋅⋅⋅ ⋅⋅⋅ Am,m

temos λ₁(A) + λ_n(A) ≤ λ₁(A)′ + λ₁(A_mm) e usando a equação (15) no lado direito ficamos com

m∑-1 λ1(A)+ λn(A) ≤ - (m - 2)λmin(A′)+ λ1(Aii)+ λ1(Amm ) i=1 ∑m ≤ - (m - 2)λn(A )+ λ1 (Aii), i=1

pois λ_min(A′) ≥ λ_n(A) por entrelaçamento. Assim λ₁(A)+(m-1)λ_n(A) ≤∑ _i=1^mλ₁(A_ii). ♦

11 Distribuição das arestas e λ

Sejam U,W ⊆ V (G), com U ∩W = ∅. Podemos formar os seguintes vetores u e w (vetores característicos dos conjuntos U e W):

( ) u1 { || u2|| 0, se i ∕∈ U u = |( ... |) ; ui = 1, se i ∈ U v n

( ) w1 { || w2 || 0, se i∈∕W w = |( .. |) ; wi = . 1, se i ∈ W wn

Definiremos e(U) como o número de arestas do grafo G induzido por U e e(U,W) como o número de arestas que ligam um vértice de U a um vértice de W:

e(U ) = |E(G [U])| e e(U,W ) = |{e ∈ E (G) : e∩ U ⁄= ∅ e e ∩W ⁄= ∅} |.

Dessa forma

∑n ∑n ⟨u, Au ⟩ = uT Au = aijuiuj = 2e(U ) i=1 j=1

(16)

∑n ∑n ⟨u,Aw ⟩ = uT Aw = aijuiwj = e(U,W ) i=1j=1

(17)

Usando a decomposição espectral de A (corolário 4, pg. 55):

A = λ1v1v1T + λ2v2v2T + ⋅⋅⋅+ λnvnvnT ◟--◝◜--◞ ◟----------◝◜----------◞ A1 E

(18)

Assim, substituindo (18) em (16) e (18) em (17) obtemos, respectivamente:

T T 2e(U ) = u A1u + u εu, e

(19)

T T e(U,W ) = u A1w + u Ew.

(20)

Substituindo o valor de A₁ no primeiro termo da soma das equações acima:

T T T T T T u A1u = u λ1v1v1 u = λ1 (v1 u) (v1 u) uT A1w = λ1(uTv1 )(v1T w)

e se escrevemos u e w na base {v₁,v₂,…,v_n} de autovetores ortonormais

u = α1v1 + α2v2 + ⋅⋅⋅+ αnvn

w = β1v1 + β2v2 + ⋅⋅⋅+ βnvn

então

T 2 T u A1u = λ1α1 e u A1w = λ1α1β1

Analogamente, substituindo o valor de

no segundo termo da soma das equações (19) e (20):

(∑n ) ∑n ∑n uTEu = uT λiviviT u = λiuTviviTu = λiα2i i=2 i=2 i=2 ∑n uT Ew = λiαiβi. i=2

Portanto:

| | | | | | ||∑n || |2e(U )- uT A1u| = |uTEu | ⇐ ⇒ |2e(U )- λ1α21| = || λiα2i|| |i=2 |

e fazendo λ = max{|λ₂|,|λ₃|,…,|λ_n|} temos

||∑n || ∑n ∑n || λiα2||≤ |λi|α2 ≤ λ α2. |i=2 i| i=2 i i=2 i

Como

∑n ∑n ∑n ||u|| = α2i = ui = |U | ⇒ α2i = |U|- α21 i=1 i=1 i=2

temos

| | ||∑n || ( ) |2e(U) - λ1α21| ≤ λ| α2i| = λ |U |- α21 . |i=2 |

(A)

De maneira análoga, para subgrafos bipartidos temos

| | ||∑n || ∘ (-------2)(--------2) |e(U, W )- λ1α1 β1| = || λiαiβi|| ≤ λ |U |- α1 |W |- β1 i=2

(B)

A última desigualdade segue de Cauchy-Schwarz:

∘ ----2---2 |⟨a, b⟩| ≤ ||a || ||b||

com os seguintes vetores a e b,

( λ α ) ( β ) | 2 2| | 2| a = || λ3α3 || ; b = || β3|| ( ... ) ( ...) λnαn βn

resultando que

| | ┌│ (--------)-(------)-- ┌│ (------)-(------)-- ||∑n || │∘ ∑n 2 2 ∑n 2 │∘ ∑n 2 ∑n 2 || λiαiβi|| ≤ λiαi βi ≤ λ αi βi i=2 ∘ i=2---------i=2---------- i=2 i=2 ( 2 2)( 2 2) ≤ λ ||u|| - α1 ||w || - β1

11.1 Grafos d-regulares

Para um grafo G d-regular temos λ₁ = d, e

( ) T ( ) | u1| | 1| α = ⟨u,v⟩ = √1--| u2| | 1| = |√U-|. 1 n |( ... |) |( ...|) n u 1 n

Assim, (A) e (B) ficam

|| d || ( 1 ) ||2e(U )- -|U|2|| ≤ λ|U| 1- √-- n ∘ --------n------------------- || d || ( |U |) ( |W |) ||e(U,W ) - -|U ||W ||| ≤ λ |U| 1- --- |W | 1- ---- n n n

11.2 Grafos não-regulares

Nesse caso, e distribuição de arestas não tem um forma fechada razoável. Vamos dar somente o resultado final sem mostrar as contas. Para um grafo G não-regular definimos

n d = d(G ) e K = ∑ (d - d )2 i i=1

ou seja, o grau médio de G e a variância dos graus dos vértices, onde d_i = d(i) é o grau do vértice i.

Nesse caso, temos

∘ -- ∘ -- || 2 d 2|| 2K |U|d+ 2K Kn-+ |U|2(d- λ)2 Kn ||λ1α1 - n-|U ||| ≤ -------------n(d--λ-)2-------------.

∘ -- n(d- λ )2 Kn- |λ1 - d| ≤--------2----- n (d - λ) + K

| | ||α2- |U-|2||≤ --2K-|U-|- | 1 n | n (d - λ)2

12 Grafos Expansores

Grafos expansores se caracterizam combinatorialmente por possuir alta conexidade e por serem esparsos. Um grafo exparso possui:

n < |E | < αn2, ∀α > 0

onde |E| geralmente é dn
2

para valores pequenos de d como √ --
n

ou log n. Idealmente, queremos d constante. Veremos exemplos de grafos d-regulares, para d-fixo, ainda assim altamente conexos.

Equivalentemente, como veremos, grafos expansores se caracterizam algebricamente por terem segundo autovalor (λ) pequeno quando comparado a λ₁.

Seja G um grafo d-regular (λ₁ = d). Para todo U e W ⊆ V (G), com U e V disjuntos:

∘ ---------------------------- || d|U||W ||| ( |U|) ( |W |) ||e(U,W )- --------|| ≤ λ |U | 1 - --- |W | 1 - ---- . n n n

(21)

Notemos que de (21), temos:

∘ ---(--------)----(--------)- d|U-||W-|- |U-| |W-|- e(U, W ) ≥ n - λ |U| 1- n |W | 1- n

e quando W = U = V (G) - U:

∘ -------- -- d- -- |U-|2|U-|2- d---λ -- e(U,U ) ≥ n|U||U|- λ n2 ≥ n |U ||U |

Teorema 79. Se d - λ ≥ 2 então G é d-aresta-conexo.

Demonstração. A prova será feita em 3 casos:

Se 1 ≤|U|≤ d, então $-- e(U,U ) ≥ |U |(d- |U |+ 1) ≥ d$
Se d ≤|U|≤ n∕2, então $e(U,U-) ≥ d--λ-|U ||U-| ≥ 2-d|U| ≥ d n n$
Se |U| > a prova é similar aos casos acima substituindo U por U.

♦

Definiremos a constante isoperimétrica(h(G)) de um grafo G como sendo:

-- h(G ) = min e(U,-U)-. U⁄= ∅ |U | |U|≤n2

Observação 80. e(U,U)∕|U| é o número médio de arestas que saem de cada vértice de U para U (grau médio de considerarmos grafos bipartidos).

Exemplo 81. Os valores de h(G) para o grafo completo de n vértices e o circuito C de tamanho n são:

n n n 4 h(K ) ∽ 2, h(C ) ∽ n-,

onde f(n) ∽ g(n) significa que f(n)∕g(n) → 1 quando n →∞.

Um grafo G d-regular é ε-espansor (ε > 0) se h(G) ≥ ε.

Teorema 82. Se um grafo G é conexo e d-regular, então:

d---λ ≤ h (G ) ≤ ∘2d-(d--1)- 2

Demonstração. Apenas d-2λ- ≤ h(G) será demonstrado. Dado U ⊆ V,0 ≤ |U|≤ temos:

e(U,U-) d - λ -- d- λn d- λ ------- ≥ -----|U| ≥ -------= -----. |U| n n 2 2

♦

Pelo Teorema 82 vemos que quanto maior o valor de d - λ melhor. Mas devemos saber o quão pequeno λ pode ser. Então enunciaremos o seguinte resultado.

Teorema 83. λ ≥ 2 -----
√ d- 1 ( ( )2)
1 - O --1-
logn .

Demonstração. Demonstraremos um caso mais simples:

( ∘ -----) √-- n---d λ ≥ d n - 1 .

O resultado segue de

n ∑ 2 2 2 2|E| = nd = λi ≤ λ1 + (n- 1)λ ⇒ i=1

2 λ2 ≥ nd---λ1= d(n---d) n- 1 n - 1

Ou seja λ = Ω( √ --
d

). ♦

Exemplo 84 (Grafos de Paley). Seja p primo com p ≡ 1 (mod 4) (existem infinitos primos dessa forma). fixamos o conjunto de vértices como V = {0,1,…,p - 1} e o conjunto de arestas é dado por ij ∈ E se, e somente se, i - j ≡ x² (mod p) para algum x ∈ V -{0}.

Os grafos assim formados são (p-1)
-2- -regular com λ = √p
-2- + 1

Exemplo 85. Para k ∈ ℕ, consideremos o grafo com vértices formados por vetores binário de tamanho k e número ímpar de 1’s, excluindo o vetor (1,1,…,1). As arestas são definidos por ij ∈ E ⇔ ⟨i,j⟩ ≡ 1 (mod 2), ou seja, o número de 1’s em comum entre i e j é ímpar. Esse grafo tem 2^k-1-1 vértices, é ( )
2k- 2 - 2 -regular e λ = 1 + 2.

Exercício 86. Prove que para todo U,W ⊂ V , disjuntos num grafo d-regular de n vértices vale:

(d - λ)|W ||U | e(U,W ) ≥ ------------. n

Exercício 87. Prove que para todo U ⊆ V , com |U|≤:

d- λ |N (U )| ≥ -2d--|U|

onde N(U) = (⋃ )
v∈U N (v)

- U.

13 λ₁, λ típicos

Nessa seção provaremos resultados análogos aos provados na seção 4 para α e χ. Vamos mostrar que 99,9% dos grafos de (n) têm valores de λ₁ próximos a n∕2 e de λ menor que εn para qualquer ε > 0, por menor que seja.

Para provar esses resultados vamos introduzir algumas notações:

r_G(C⁴;i) denota o número de triplas (v₀,v₁,v₂) ∈ V ³ tais que (i,v₀,v₁,v₂,i) é um circuito de comprimento 4 em G e
$∑n rG (C4) = rG(C4; i); i=1$ (22)
r_G(P²;i) denota o número de pares (v₀,v₁) ∈ V ² tais que (i,v₀,v₁) é um caminho de comprimento 2 em G e
$n 2 ∑ 2 rG(P ) = rG (P ;i). i=1$ (23)

Com a notação acima temos que

∑n tr(A4) = rG(C4) + rG(P2) + d(i)2 i=1

pois lembrando que

∑ n ∑n ∑n A4 = (bij) e bii = aimamlalkaki m=1 l=1k=1

e na diagonal de A⁴ as seguintes configurações contribuem nessa soma:

O principal resultado dessa seção é o seguinte. As hipóteses do teorema apresentadas na equação (24) valem para quase todo grafo em (n) mas essa demonstração será adiada.

Teorema 88. Para quase todo G vale o seguinte: por menor que seja δ > 0 existe ε > 0 tal que, se

2 4 e(G) > (1- ε)n-- e rG (C4 ) < (1 + ε)n- 4 16

(24)

então

n |λ1 - 2| < δn e λ < δn

(25)

para todo n suficientemente grande.

Demonstração. Dado δ > 0 tomamos ε = min{δ, 176 δ⁴}.

Um limitante inferior para λ₁ é

2 2|E-| 2(1---ε)n4- n- λ1 ≥ d(G) = n > n = (1- ε)2 .

(26)

Para a cota superior, começamos com uma estimativa generosa para r_G(P²):

∑n ∑ rG(P2) = r(P 2;i) = (n- 1 )(n - 2) = O(n3). i=1 i

(27)

Ainda, similarmente, ∑ _id(i)² = O(n³). Agora,

n 4 ∑ 4 4 2 ∑ 2 λ 1 ≤ λi = rG(C )+ rG(P )+ d(i) i=1 i n4- 3 3 < (1+ ε)16 + O (n )+ O (n ) n4 ε 4 < (1+ ε)16-+ 16-n 4 = (1+ 2ε)n-- (28) 16 4n4- < (1+ 2ε) 16

e λ₁ < (1 + 2ε)n∕2 < (1 + δ)n∕2 que, junto com (26) resulta em

| n| ||λ1 - -|| < δn. 2

Para o segundo autovalor, supomos que λ = δn para algum δ positivo e, sem perda de generalidade, que λ = |λ₂|). Com essas hipóteses temos

∑n 4 4 4 ∑n 4 n4- λ1 = λ1 + λ 2 + λ i < (1 + 2ε)16 i=1 i=3

onde a última desigualdade vem de (28). Pela escolha de ε ficamos com

∑n 4 λ41 < (1 + 2ε)n--- λ41 - λ4 i=3 16 4 4 < (1 + 2ε)n--- (1 - ε)4n--- δ4n4 ( 16 16 ) 2 3 4 δ4- n4- = 6ε- 6ε + 4ε - ε - 16 16 ( δ4) n4 < 6ε+ 4ε3 - --- ---< 0 16 16

Uma contradição, logo λ < δn ♦

Da modo semelhante prova-se os seguintes resultados.

Proposição 89. Para quase todo G ∈(n) o grau médio satisfaz

| n | ||d(G )- --|| < δn 2

para qualquer δ > 0 se n for suficientemente grande.

Demonstração. Exercício. ♦

Corolário 8. Para quase todo G ∈(n)

∑n || n || 2 |d(i)- 2-| < δn i=1

(29)

para qualquer δ > 0 se n for suficientemente grande.

Usando Cauchy-Schwarz obtemos o seguinte resultado.

Corolário 9. Para quase todo G ∈(n) vale que: para todo γ > 0 existe δ > 0 tal que se (29) então

|| n|| |d(i) - -| < γn 2

para pelo menos (1 - α)n vértices, para qualquer α > 0.

Exercício 90. Mostre que para quase todo G ∈(n) vale cada um dos seguintes itens.

|λ₁ -| < ε.
|e(U) -| < εn².
|e(U,W) -| < εn².

13.1 e(G) e r_G(C⁴) típicos

Foi assumido no teorema 88 que para um ε > 0 quase todo G ∈(n) satisfaz

2 e(G) > (1 - ε)n-- 4 r (C4) < (1 + ε)n4- G 16

Vamos mostrar que:

| 4| 4 ||rG(C4 )- n--||< εn-- | 16 | 16

vale para quase todos os grafos de

(n). O que de fato mostraremos é que o contrário vale para poucos (0,1%) grafos

|{ } | || G ∈ G (n ): |rG (C4)- n4| > εn4 || ----------------------16----16---< 0,001 2N

para todo n suficientemente grande, onde |

(n)| = 2^N e N = (n 2) .

Para tal objetivo precisamos de algumas ferramentas. Seja X : →ℕ uma função cuja média é

∑ X (G ) μX = --G∈G(n)------. 2N

Dessa forma, se considerarmos apenas os grafos que têm um valor alto de X, digamos X(G) ≥ t₀, obtemos

-1- ∑ 2N X (G) ≤ μX GX(∈GG)(n≥)t 0

por um lado e

∑ X (G ) ≥ t0|{G ∈ G(n): X (G ) ≥ t0}| G∈G(n) X (G )≥t0

por outro e, das duas equações ficamos com a desigualdade de Markov

|{G ∈ G(n): X (G ) ≥ t }| μ -----------N--------0--≤ -x. 2 t0

(30)

Como estamos interessado em quanto o valor de uma função desvia de sua média passamos a considerar a seguinte função

Y(G ) = (X (G )- μX )2

cuja média é

μY = μX2 - (μX )2.

Substituindo Y e μ_Y da desigualdade de Markov (30) obtemos a desigualdade de Chebyschev:

|{G ∈ G (n): |X - μ | ≥ t }| μ - (μ )2 ------------N-----x----0--≤ -X2----2X--. 2 (t0)

Voltando a r_G(C⁴), definimos (n)₄ = n(n - 1)(n - 2)(n - 3)(n)_k) o número de sequências (a,b,c,d), todas diferentes, tomadas de n letras. Seja e C₁,C₂,…,C_(n)₄ uma enumeração das quadruplas (a,b,c,d) e definimos as funções indicadoras

{1, se C define um circuito de comprimento 4 em G Xi(G) = i 0, caso contr´ario.

Claramente

4 (n∑)4 rG(C ) = Xi(G ) e i=1 (n∑)4(∑n)4 (n∑)4 (n∑)4 (rG(C4 ))2 = Xi (G )Xj(G ) = Xi2 + Xi(G )Xj(G ). i=1 j=1 i=1 j=1 j⁄=i

O valor médio de r_G(C⁴) é

(n)4 ∑ (n-)4 μXi = 24 . i=1

Observamos que o valor médio de X_i² é o mesmo de X_i e assim

(n)4 ∑ (n)1 μXi2 = 24 . i=1

Dessa forma resta calcularmos

∑ Xi(G )Xj(G ) μXiXj = --G-----N-------. 2

Abaixo, apresentamos uma tabela aonde na primeira coluna desenhos o diagrama dos tipos de isomorfismo possíveis para C_i e C_j fixos, na segunda coluna temos a fração de grafos que contém esses C_i e C_j e finalmente na terceira apresentamos o número de pares (i,j) para os quais essa fração contribui na soma.

Dessa forma a média da função r_G(C⁴) ao quadrado fica

(n) (n) (n) (n ) (n) μ(rG(C4 )2) = --44 + --88+ --87+ -76-+ --65 2 2 2 2 2

e aplicando-a em Chebyschev

μ(r (C4 )2) - (μ(r (C4)))2 (n)4-+ (n)7-+ (n)6-+ (n)5- ---G--2--------4-G2------ < -24-----28(----27)2----26-- ε(μ(rG (C ))) ε2 (n)44- ( 2 ) 1- -24- (n---4)3- 2(n---4)2 22(n---4) = ε2 (n)4 + (n)4 + (n)4 + (n)4 ◟----------------2-◝◜-------------------◞ <1ε000 se n grande < 0,001.

Dessa forma provamos que

|{ | | } | || || 4 n4|| n4- || N | G ∈ G(n): |rG (C )- 16| > ε 16 | < 0,0012 ♦

13.2 Número de arestas típico.

Esta seção estabelece o número típico de arestas para 99,99% dos grafos de (n).

Se denotamos por μ = μ(e(G)) o número médio de arestas de um grafo então a desigualdade de Chebyschev fica

|{G ∈ G(n): |e(G )- μ| > εμ}| μ (e(G )2)- μ2 --------------N--------------< -------2-----. 2 εμ

Proposição 91. Para quase todo grafo G ∈ (n), o seguinte fato é verdadeiro:

| 2| ||e(G )- n-||< δn2 | 4 |

por menor que seja δ, se n é suficientemente grande.

Demonstração. Definimos e₁,e₂, ⋅⋅⋅ ,e_N como a enumeração de pares de vértices, sendo N = ( )
n2 . Definimos

{ ei(G ) = 1, se ei ∈ E(G ) 0, caso contrario.

Claramente

N N N N ∑ 2 ∑ ∑ ∑ e(G) = ei(G ) e e(G ) = ei(G )+ ei(G )ej(G ). i=1 i=1 i=1 j=j⁄=1i

Dessa forma,

N ∑ N- μ = μ (ei(G )) = 2 i=1

pois

∑ ei(G) |{G : ei ∈ E(G )}| 1 μ(ei) =---G2N--- = -------2N------- = 2-.

Fixados i e j distintos

∑ N-2 μ (eiej) = --G-ei(G-)ej(G-)= 2----= 1- 2N 2N 4

portanto

N N 1 N2 N μ = -- e μ (e(G )2) =-- + --N(N - 1) = ---+ -- 2 2 4 4 2

e o lado esquerdo da desiguladade de Chebyschev fica

2 2 N- μ(e(G)2-)2--μ--= --22-< ε2(0,001), ε μ ε2N4-

para todo n é suficientemente grande. ♦

14 Laplaciano

A fim de definirmos a matriz laplaciana, é conveniente relembrarmos alguns conceitos:

A matriz de adjacências A(G) = (a_ij) para um grafo G com vértices V (G) = {1,2,…,n}, é definida como: $( { 1, se ij ∈ E (G) aij = ( 0, se ij∈∕E (G)$
A matriz diagonal é definida como: $( ) a1 0 ⋅⋅⋅ 0 || 0 a2 ⋅⋅⋅ 0 || diag(a ,a ,...,a ) = || .. .. .. .. || 1 2 n | . . . . | ( 0 0 ⋅⋅⋅ an)$
d(i) é o grau do vértice i.

Se definirmos a matriz D(G) como D(G) = diag(d(1),d(2),…,d(n)) a matriz laplaciana L(G) é a matriz :

L (G ) = D(G )- A (G)

(31)

e se l_ij é o elemento da matriz L(G) na linha i e coluna j, então

( | - 1, se i,j ∈ E { lij = |( d(i), se i = j 0, caso contr´ario.

A matriz Laplaciana de G também pode ser obtida através da multiplicação da matriz Q pela sua transposta

T L = QQ

onde Q é a matriz |V (G)|×|E(G)| cuja definição é:

( |{ 1, se i = min(e) qie = - 1, se i = max (e) |( 0, caso contr´ario.

Cada elemento da matriz laplaciana, portanto, pode ser obtida através de:

(QQT ) = ∑ q q ij ie je e∈E

de forma que cada um dos dois elementos do somatório pode assumir valores 0, 1 ou -1. Tomando-se as linhas da matriz Q, duas situações podem ocorrer. Se as linhas multiplicadas forem coincidentes, isto é, i = j:

∑ 2 (qie) = d (i). e∈E

Por outro lado, se as linhas forem diferentes, isto é, i≠j:

( ∑ |{ qieqje = - 1, se {i,j} ∈ E qieqje = 0, se {i,j} ∕∈ E . e∈E |(

(32)

Esses dois valores ocorrem devido ao fato de não termos uma coluna em Q que possua dois valores -1 ou dois valores 1.

Para um vetor v qualquer, v = (v₁,v₂,…,v_n)^T temos

T ( T ) ( T ) ( T )T ( T ) v Lv = v Q Q v = Q v Q v .

Considerando que e = {i,j} e i < j

∑n ∑n (QT v) = (qek)T vk = qkevk = (vi - vj) e k=1 k=1

logo

(QT v)T (QT v) = ∑ (v - v )(v - v ) = ∑ (v - v )2 i j i j i j ij∈E ij∈E

(33)

ou seja, v^TLv ≥ 0, ∀v, e por definição temos:

Proposição 92. L é positiva e semidefinida.

Corolário 10. Autovalores de L são não-negativos.

Exercício 93. Mostre que 0 é autovalor com autovetor

( ) 1 ||1|| 1 = |( ...|) . 1

O espectro de L(G) é a seqüência de seus autovalores em ordem não-decrescente

SpL = (μ1,μ2,...,μn). (34)

com 0 = μ₁ ≥ μ₂ ≥… ≥ μ_n.

Exercício 94. Prove que se Δ(G) = d(v₁) ≥ d(v₂) ≥ … ≥ d(v_k) então μ_n ≤ d(v₁) + d(v₂).

Lema 95. A multiplicidade algébrica de μ₁ é igual ao número de componentes conexas de G.

Demonstração. Sejam C uma componente conexa de G, e

( ) c1 || c2|| c = |( ...|) c n

seu vetor característico, ou seja,

{ ci = 1, se i ∈ C 0, caso contr´ario.

Da definição temos

∑ ∑ (Lc)i = lijcj = liici + lijcj = 0(∀i ∈ [n]) j j⁄=i

Isso implica que 0 é uma autovalor de L com c autovetor associado. Se G tem t componentes conexas os t vetores característicos são autovetores de 0 e são ortogonais, portanto a dimensão do autoespaço V _μ₁ é pelo menos t.

Por outro lado, se x é um autovetor de 0 então

T ∑ 2 0 = x Lx = (xi - xj) ij∈E

que implica em x constante em cada componente conexa de G, ou seja, x é uma combinação linear dos vetores característicos das componentes e, portanto, dimV _μ₁ ≤ t.

Como ma(μ₁) = mg(μ₁) temos que t é a multiplicidade algébrica de μ₁. ♦

14.1 Autovalores da matriz laplaciana

Observação 96. Para grafos d-regulares, se L(G) é a matriz laplaciana com autovalores {μ₁,…,μ_n} e A(G) é a matriz de adjacência com autovalores {λ₁,…,λ_n} então, por definição

L(G) = D - A (G) = d⋅ Id - A (G )

portanto o polinômio característico de L(G) é

p (x) = det(L - xId) = det((d - x)Id- A) = det(A - (d - x)Id) L

e como p_A(x) = det(A - xI) podemos concluir as seguintes relações entre os autovalores de A(G) e L(G)

μi = d - λi.

Proposição 97. Tome G um grafo e μ₁ ≤ μ₂ ≤… ≤ μ_n os autovalores de L(G) em ordem não-decrescente. Então

∑ 2 ----ij∈E(xi --xj)--- μ2 = 2n mxi⊥n1 ∑ni=1∑nj=1(xi - xj)2.

(35)

Ainda, para qualquer constante c ∈ ℝ,

∑ (x - x )2 μ2 = 2n min ∑n---ij∈∑En---i---j----. x⁄=c⋅1 i=1 j=1(xi - xj)2

(36)

Demonstração. Para provar a equação (35), observe que

∑n ∑n (xi - xj)2 i=1 j=1 n n n n n n = ∑ ∑ x2 - 2∑ ∑ x x + ∑ ∑ x2 i i j j ni jn in jn ni jn ∑ ∑ 2 ∑ ∑ ∑ ∑ 2 = xi - 2 xixj + xj j i i j i j ∑n ∑n = n ⟨x,x⟩- 2 xi xj + n⟨x,x ⟩ i j = 2n ⟨x,x⟩- 2⟨x,1 ⟩2 = 2n⟨x,x ⟩

pois x é ortogonal a 1. Então

∑ xT-Lx- ----ij∈E(xi --xj)2-- μ2 = mxi⊥n1 xTx = 2n mxi⊥n1 ∑ni=1∑nj=1(xi - xj)2 .

Para a equação (36), observe que

∑ ∑ --ij∈E((xi +-c)--(x2-+-c))2 --ij∈E-(xi---xj)2- ∑ ∑ ((xi + c)- (xj + c))2 = ∑ ∑ (xi - xj)2. i j i j

♦

Proposição 98. Se δ(G) é o grau mínimo de G e μ₁ ≤ μ₂ ≤… ≤ μ_n os autovalores de L(G), então

μ2 ≤ --n--δ(G). n - 1

Demonstração. Tome e_i o vetor característico do conjunto unitário {i}. Por (36)

∑ (x - x )2 μ2 ≤ 2n∑n---ij∑∈nE--i----j----= 2n --d(k)--= --n--d(k), i=1 j=1(xi - xj)2 2(n - 1) n- 1

para todo k ∈ V . Em particular, a desigualdade é válida para o k tal que d(k) = δ(G). ♦

Exercício 99. Mostre que

∑ -----ij∈E-(xi---xj)2-- μn = 2n mxa⊥xc⋅1∑n ∑n (xi - xj)2. i=1 j=1

Exercício 100. Sendo Δ(G) o grau máximo de G, mostre que

n 2Δ (G ) ≥ μn ≥ -----Δ (G). n - 1

Proposição 101. Se U ⊆ V e |U|≤ |V|
2 , então

-- e(U, U) ≥ μ2|U|. 2

Demonstração. Se u é o vetor

{ 1-- u = |U| se i ∈ U i - -1- se i ∕∈ U |U|

então

∑n 1 - 1-- ⟨u,1⟩ = ui = ---|U|+ ---|U | = 0 i=1 |U| |U |

Como u é ortogonal a 1,

T ∑ (u - u )2 ( 1-+ -1)2 ⋅e(U, U) μ2 ≤ u-TLu-= --ij∈E∑n--i2--j--= -|U|---|U-|---------- u u i ui ||UU||2 +-|U-|2 |U|

= (-1- + -1-)e(U,U-) ≤ 2--e(U, U) ⇒ e(U, U) ≥ μ |U| |U| |U| |U | 2 2

♦

Referências

[1] M. Aigner, G. Ziegler, As provas estão n’O livro, Editora Edgar Blücher, 2002. (Seções 1 e 2)

[2] P. Feofiloff, Y. Kohayakawa, Y. Wakabayashi, Uma Introdução Sucinta à Teoria dos Grafo, II Bienal da SBM, 2004. (Seções 3 e 4)

[3] D. Poole, Álgebra Linear, Thompson, 2004. (Seções 5, 6, e 7)

[4] K.Y. Lin, An elementary proof of the Perron-Frobenius theorem for non-negative symmetric matrices, Chinese Journal of Physics 4(15), 1977. (Seção 8)

[5] L. Babai, Linear Algebra and applications to graphs, Discrete Mathematics REU, Summer 2002. Disponível em novembro de 2005 no sítio http://people.cs.uchicago.edu/~laci/reu02/. (Seções 9 e 10)

[6] M. Krivelevich and B. Sudakov, Pseudo-random graphs. Disponível em novembro de 2005 no sítio http://www.math.princeton.edu/~bsudakov/papers.html. (Seção 11)

[7] Nati Linial and Avi Wigderson, Expander Graphs and their Applications - Lecture notes, Spring 2002. Disponível em novembro de 2005 no sítio http://www.math.ias.edu/~avi/TALKS/. (Seção 12)

[8] N. Alon and J. Spencer, Probabilistic Methods, Wiley, 2nd. ed., 2000. (Seção 13)

[9] Bojan Mohar, Some Applications of Laplace Eigenvalues fo Graphs, in Graph Symmetry: Algebraic Methods and Applications, Eds. G. Hahn and G. Sabidussi, Kluwer, 1977, pp. 225–275. (Seção 14)

Tópicos em Teoria dos Grafos — Métodos da Álgebra Linear em Teoria de Grafos —

Sumário

1 Grafos extremais sem triângulos

2 Grafos extremais sem Kp

3 Coloração de vértices

4 α e χ típicos

5 Matrizes

6 Autovalores e autovetores

7 Matrizes simétricas e o Teorema Espectral

8 Teorema de Courant-Fischer e Teorema de Perron-Frobenius

9 Teoria Espectral de Grafos

9.1 Grau

9.2 Subgrafos

9.3 Conexidade

9.4 Grafos bipartidos

10 α,χ,ω,λ

11 Distribuição das arestas e λ

11.1 Grafos d-regulares

11.2 Grafos não-regulares

12 Grafos Expansores

13 λ1, λ típicos

13.1 e(G) e rG(C4) típicos

13.2 Número de arestas típico.

14 Laplaciano

14.1 Autovalores da matriz laplaciana

Referências

Tópicos em Teoria dos Grafos
— Métodos da Álgebra Linear em Teoria de Grafos —

2 Grafos extremais sem K^p

13 λ₁, λ típicos

13.1 e(G) e r_G(C⁴) típicos