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 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

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 = Gn é 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 K3, 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 Kn1,n2,,np-1 o grafo (p-1)-partido completo onde as partes têm cardinalidades n1,n2,,np-1. Mostre que dentre os grafos (p - 1)-partidos completos com n vértices o número máximo de arestas é atingido quando |ni - nj|1 para todos i,j [p - 1].

Em 1941, Paul Turán provou que esse grafo é extremal com relação a conter Kp. Mais que isso, esse grafo é único1 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 Kp

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

Demonstração. Seja Gn um grafo extremal sem Kp. Vamos mostrar que em Gn 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 ua todos os vértices de N(u). Esse grafo resultante tem ordem n e d(u) - d(v) arestas a mais que Gn; também (exercício) não contém Kp, um absurdo pois Gn é 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 ve em v′′. Novamente, o grafo obtido tem mais arestas que Gn e não contém Kp, 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 Gn 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 Erd˝o  s e Stone. O Teorema de Erd˝o  s–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 Kp mas um Kp(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 n0 > 0 tal que todo grafo com n n0 vértices e pelo menos

  (     )            ( )
1- p---2  (n2 - r2) +  r  + ρn2
2  p - 1              2
arestas, contém uma cópia do Kp(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 limn→∞f(n) = 0.

O Teorema de Erd˝o  s–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 1 V 2 ⋅⋅⋅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 = Gn

χ(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 = Gn

χ(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 1,V 2,,V k} uma coloração própria de H.

Se k < Δ(G) + 1 então {{v},V 1,,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 dG(v) Δ(G). Dessa forma podemos tomar a coloração própria {V 1,V 2,,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 K1,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 G(n) como o conjunto de todos os grafos sobre V . Claramente |G(n)| = 2N, onde N = ( )
 n2.

Denotamos por Qk(n) o conjunto dos grafos G G(n) tais que α(G) k. Para estima a cardinalidade desse conjunto, fixamos X [n] de cardinalidade k. Os grafos de G(n) nos quais X é um conjunto independente podem ser identificados numa relação de um-para-um com os subconjuntos de V (2) \ X(2), onde X(2) é 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 G(n).

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

        -----n------
χ (G) > ⌈(2+ ε)lgn ⌉
para quase todo G G(n).

Acima, para quase todo significa que |P(n)||G(n)|→ 1 conforme n →∞, onde P é 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 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 = (ai,j) a matriz cuja entrada na i-ésima linha e j-ésima coluna é ai,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

  1. tr(AB) = tr(BA).
  2. (AB)* = B*A*.
  3. det(AT) = det(A).
  4. det(AB) = det(A)det(B).
  5. Se A ~ B então det(A) = det(B).
  6. 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

  1. A é invertível;
  2. Ax = 0 tem apenas a solução trivial;
  3. os vetores coluna de A são linearmente independentes;
  4. 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 ai,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 v0 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 = 1 e λ2 = -2.

Os autovetores associados a λ1 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 λ2 são

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

Exemplo 15. Para a matriz

     (      )
       1  0
A =  ( 1  - 2)
temos autovalores λ1 = 1, com autovetores V λ1 = {(3a)
 a: a *}; e λ2 = -2, com autovetores V λ2 = {( )
 0b: b *}.

Exemplo 16.

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

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

Os autovetores associados a λ1 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 λ2 = -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 pA(x) = (3-x)(-1-x)2, com raízes (3,-1,-1), portanto autovalores λ1 = 3 com multiplicidade 1 e λ2 = -1 com multiplicidade 2.

Autovetores associados a λ1

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

Autovetores associados a λ2

     (  (  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 λ1 um autovalor então

           3
Vλ = {v ∈ ℝ : Av = λv }
é um subespaço do 3.

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 λ1 = 2.

Se λ é autovalor de A, então V λ = {v n : Av = λv}é subespaço de n (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 pA(x) = 0, isto é, o número de fatores (x - λ) no polinômio característico da matriz.

Compare as multiplicidades nos exemplos 1417 acima.

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

mg (λ ) ≤ ma (λ).

Demonstração. Sejam A matriz, λ autovalor, V λ n auto-espaço e p = mg(λ) = dimV λ. Sejam {v1,v2,,vp} ∈ V λ vetores linearmente independentes, e {v1,v2,,vp,u1,,un-p} o conjunto completado para uma base do n. 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 pA(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, λ1,k autovalores distintos, e v1,,vk 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 vi+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(x1,,xn) 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 ui são autovetores.

Prova-se a recíproca considerando a matriz invertível P = (u1,,un), onde ui 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 pA(x) = pB(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 n um número real u,v, que satisfaça as seguinte condições (axiomas):

  1. u,v= v,u.
  2. Cu,v= Cu,v   (C ).
  3. u,v + w= u,v+ u,w.
  4. u,u= 0 u = 0.

O Produto Interno canônico em n é 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

  1. u,Cv= Cu,v   (C ).
  2. u + v,w= u,w+ v,w.
  3. 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 λ1 e λ2 autovalores distintos com respectivos autovetores u e v. Vamos mostrar u,v= uTv = 0.

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

Logo, temos (λ1 - λ2)uT v = 0, como λ1 - λ20, pois são diferentes, temos uT v = 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 2u,v)2 - 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||2||1||2 d,12, 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 {u1,u2,,un} do n podemos obter, através de projeções ortogonais, uma base ortogonal {v1,v2,,vn} 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 vi’s de modo a formarmos uma base ortonormal.

Uma matriz é dita ortogonal se suas colunas formam um conjunto de vetores ortonormais no n. Equivalentemente, QTQ = Id, pois se Q = (q1,,qn) temos:

(    )
  q1T                (          )
| q2T|                 1      0
||  . || (q1,...,qn) = |(    ...   |) ,
(  .. )                 0       1
  qnT
pois
qiTqi = ⟨qi,qi⟩ = 1eqiTqj = ⟨qi,qj ⟩ = 0.

Observação 29. QT = Q-1

Exercício 30. Mostre que

  1. ||Qv|| = ||v||.
  2. Qu,Qv= u,v.
  3. 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 n 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 QTAQ = diag(λ12,n), onde λ12,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 λ12,k autovalores distintos de A e u1,u2,,uk autovetores linearmente independentes associados aos autovalores. Completamos {u1,u2,,uk} para uma base {u1,u2,,uk,uk+1,,un} do n.

Usando Gram-Schmidt, podemos tomar uma base ortonormal

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

Observamos que v1 é um autovetor de A. Agora tomemos Q1 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 BT = (Q1TAQ1)T = Q1TAQ1, temos que A1 é simétrica e, portanto, existe Q2 ortogonal tal que Q2TA1Q2 = diag(μ12,n-1) com μi autovalor de A1 para todo i.

Tomemos então Q3

         (             )
         |λ1  0  ...  0|
Q    =   | 0           | ,
  3      |( ...     Q2    |)
           0
e, finalmente, Q = Q1Q3. Claramente, Q3 é 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 μ1,n-1 são autovalores de A1.

Exercício 34. Se A = (      )
  D  B
  0  C com D e C matrizes quadradas, então pA(x) = pD(x)pC(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 {v1,v2,,vn} 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 λ1 λ2 λn os autovalores de A. Então

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

Demonstração. Por definição Ax,x= xTAx. Pelo Teorema 33, podemos escrever A = QDQT. Portanto xTAx = xTQDQx = (QTx)TD(QTx) e fazendo y = QTx 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 λ1 λ2 λ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, λ1 λ2 λn autovalores de A com respectivos autovetores ortonormais q1,q2,,qn. 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 = QTx. De ||x|| = 1 temos ||y|| = 1 e, também do exercício 30, de temos que QTx,QTq1= x,q1= 0, ou seja, y QTx. Ainda,

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

Após a resolução análoga à proposição anterior, obtemos ao invés de λ1y12 + λ2y22 + + λnyn2 a expressão 0 + λ2y22 + λ3y32 + + λnyn2 e como λ2 é 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 λ1 λ2 ⋅⋅⋅λn. Então

λk =  max  min ⟨Ax,-x⟩,
     dimUU=kxx∈⁄=U0  ⟨x,x⟩
onde U varia sobre todo subespaço do n de dimensão k.

Demonstração. Seja U um subespaço qualquer de dimensão dim = k e q1,,qn autovetores ortonormais associados a λ12,n, respectivamente.

Tomamos os subespaços V k = [q1,,qk], e Tk = [qk+1,,qn] e, como dimU = k temos que existe x uTk-1{0} pois dimTk-1+dimU = n+1.

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

    ∑n
x =     αiqi.
    i=k

Seja Q = (q1,,qn) a matriz ortogonal de autovetores e façamos y = QTx. 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=1kαiqi 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 n.

Proposição 41 (Teorema do Entrelaçamento). Seja A = (ai,j) matriz simétrica com autovalores λ1 λ2 λn e Ak = (ai,j)i,jk matriz (n - 1) × (n - 1) simétrica, com autovalores μ1 μ2 μn-1. Então

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

Demonstração. Vamos mostrar que λj μj λj+1 para A1. 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 {u1,u2,,un} uma base de U. Definimos
     (   )
 ′     0
ui = ( ui)     (∀i = 1,2,...,j)
sendo Uo subespaço [u1,u2,,uj] no Rn 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 A1.

Para mostrar μj λj+1 para A1 usamos o exercício 40. Os detalhes ficam como exercício.

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

Exemplo 42. Suponha a permutação 3214567, ou seja, ρ(1) = 3(3) = 1(i) = i(i1,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

  1. Aρ = PAPT;
  2. Aρ tem os mesmos autovalores de A;
  3. 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 (aij 0), irredutível e com autovalores λ1 λ2 λn. Então

  1. λ1 > 0 e existe autovetor não-negativo associado v1;
  2. λ1 > λ2;
  3. |λi|λ1 para todo i = 2,,n;
  4. λ1 = -λn se, e só se, existe ρ tal que Aρ = (       )
( 0T  B )
  B   0.

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

Seja u autovetor com norma 1 associado a λ1. 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 λ1 não-negativo e tem norma 1.

Suponha que existam i’s tais que ui = 0. Seja ρ uma permutação tal que |Ui| > 0 para todo i m e |ui| = 0 pra todo i > m. Escrevendo Aρ = ( B  C )
(      )
  D  E e (v1)ρ = ( 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, v1 > 0.

Agora vamos mostrar que λ10. Supondo λ1 = 0 temos

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

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

(2): Vamos mostrar que λ1 > λ2.

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

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

     ( u + |u |)
     |  1    1 |
u′ = || u2 +.|u2|||
     (    ..    )
      un + |un|
autovetor de λ1. Claramente, ui + |ui|0(i) e, portanto, ui + |ui| > 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, uTv = 0 e, dessa forma, no podemos ter uivi > 0 para todo i. Absurdo. Assim, mg(λ1) = 1 e λ1 > λ2.

(3): |λ |
  iλi(i). Se vi 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 v1 é 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 -λ1 é autovalor então seja v um autovetor unitário de -λ1.

                      ||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 λ1 (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 )(  ′)
  v′′
( v ) = λ1(  ′)
  v′′
(v  ) (   ′     ′′)
 Bv ′+ Cv ′′
(Dv  +  Ev ) = (    ′)
  λ1v′′
( λ1v ) e (      )
 B   C
(D   E )(     )
   v′
( - v′′) = -λ1(     )
   v′
( - v′′) (           )
  Bv ′ - Cv ′′
( Dv ′ - Ev ′′) = (      )
  - λ1v ′
( λ1v ′′) 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 = CT

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) = (aij), onde

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

Definimos, ainda, o espectro Sp(G) = (λ12,n) do grafo G, com λ1 λ2 ⋅⋅⋅λn os autovalores reais de A.

Exemplo 47 (Grafo completo Kn). O polinômio característico pA(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 Kr,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 dij da matriz Ak é o número de seqüências (i,x1,x2,,xk-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,x1,x2,,xk-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 dij da matriz Ak é 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, dii é o número de passeios (i,l,m,k,i). Assim, dii 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), bi, mais as seqüências da forma (i,a,i,b,i), ab.

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, dii é 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(A2) = tr(D2) = i=1nλi2.

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=1nλik é 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 λ1o maior autovalor de A(G), então d(G) λ1 Δ(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 λ1 e seja vk = maxivi. Então,
       ∑n        ∑n
λ1vk =    akivi ≤    akivk = dkvk ≤ Δ (G)vk
       i=1        i=1
logo, λ1 Δ(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 λ1(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, λ1 = k.

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

Demonstração. Temos que λ1 = 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 à λ1. Logo,

             (   )   (   )
             |d1 |   | λ1|
             |d2 |   | λ1|
A1 =  λ11 ⇔  |( ... |) = |(  ...|)  .
              d        λ
               n         1
ou seja, G é λ1-regular.

9.2 Subgrafos

Teorema 59. Se Sp(G) = (λ12,n) e Sp(G - v) = (μ12,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 λ1(H) λ1(G).

Demonstração. Seja B a matriz de adjacências de H = (V (G),E(H)), então λ1(H) = v1TBv1, com v1 = (   )
  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, λ1(H) λ1(G).

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

9.3 Conexidade

Proposição 63. Seja G um grafo com componentes conexas C1,C2,,Cm, então existe uma permutação σ de 1,2,,n tal que

      (                    )
      | A11   0   ...    0 |
      |  0   A22  ...    0 |
A σ = ||  ...    ...   ...    ... ||  ,
      |(  0    0   ...  A   |)
                        mm
onde Aii é matriz de adjacência da componente conexa Ci.

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 λ1 > λ2.

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

Observação 67. Se um grafo G tem λ1 > λ2, 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(λ1) é o número de componentes conexas de G.

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

     (   )
     | v1|
v =  | v2|
 1   |(  ...|)
       v
        n
autovetor associado a λ1, 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, v1 máximo implica que vj = v1 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, vj = 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, vj = vt para todo j N(t). Como antes, temos vj = vt para todo j C(t), onde C(t) é a componente conexa que contém o vértice t.

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

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 λ1 = -λn então G é bipartido.(Dica: sinal(vj) = sinal(N(vj)) = sinal(N(N(vj))) = .)

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 λ1 √-------
 ΔA ΔB

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

          √ ------√ -----
λ1 ≤ min{2  Δ - 1,  n - 1}.
(Dica: λ1 = -λn e tr(A2) 2n - 2.)

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

  1. λ1 = -λn;
  2. λi = -λn+1-i (i);
  3. 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) λ1(G) + 1, onde λ1(G) é o maior autovalor de A(G).

Teorema 76. Se Sp(G) = (λ12,n) então

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

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

     (v )
     | 1.|
v =  ( ..)  > 0
      vn
um autovetor positivo associado a λ1. Tome σ uma permutação tal que
     (     )    (   )
       vσ(1)      u1
     |   .. |    |  ..|
vσ = (   . )  = (  .)
       vσ(n)      un
e u1 u2 un.

Para qualquer vértice i definimos o conjunto X = X(i) = {j V : ij E e j < i} e temos que X λ1 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 λ1 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 1V 2⋅⋅⋅V m com E(G[V i]) = 0. Existe uma permutação σ tal que
      (                           )
        A11     A12    ⋅⋅⋅    A1m
      ||   ...      ...     ...      ... ||
A σ = |( Am1     Am2    ⋅⋅⋅    Amm |)
com Aii = 0, quadrada (i ∈{1,,m}) e, quando ij, com Aij = 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 Aii quadrada vale que
λ1(A) + λn(A) ≤ λ1(A11)+  λ1(A22 )
onde λ1 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 - λ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 λ1(C) = max{λ1(A11)1(A22)}. Vamos supor, sem perda de generalidade, que λ1(C) = λ1(A11). 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) = -λ1(B).

Portanto, λ1(A) + λn(A) λ1(A11) + λ1(A22).

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 λ1(A) + λn(A) λ1(A)+ λ1(Amm) 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 λ1(A)+(m-1)λn(A) i=1mλ1(Aii).

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)

e

                   ∑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 A1 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 {v1,v2,,vn} 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 E 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{|λ2|,|λ3|,,|λ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 λ1 = 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 di = 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 λ1.

Seja G um grafo d-regular (λ1 = 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:

  1. Se 1 ≤|U|≤ d, então
        --
e(U,U ) ≥ |U |(d- |U |+ 1) ≥ d
  2. Se d ≤|U|≤ n∕2, então
    e(U,U-) ≥ d--λ-|U ||U-| ≥ 2-d|U| ≥ d
           n           n
  3. Se |U| > n
2 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|≤n2 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 x2 (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 2k-1-1 vértices, é (       )
2k- 2 - 2-regular e λ = 1 + 2k-23.

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|≤n2:

         d-  λ
|N (U )| ≥ -2d--|U|
onde N(U) = (⋃         )
   v∈U N (v)- U.

13 λ1, λ 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 G(n) têm valores de λ1 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:

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 A4 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 G(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 ε = 12 min{δ,176δ4}.

Um limitante inferior para λ1 é

                            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 rG(P2):

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

Ainda, similarmente, id(i)2 = O(n3). 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 < (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 λ = |λ2|). 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 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 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 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 G(n) vale cada um dos seguintes itens.

  1. |λ1 -|U-|
√n| < ε∘ ---
  |U|.
  2. |e(U) -|U|2
 4| < εn2.
  3. |e(U,W) -|U-||W|
  2| < εn2.

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

Foi assumido no teorema 88 que para um ε > 0 quase todo G 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 G(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 |G(n)| = 2N 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) t0, 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 rG(C4), definimos (n)4 = 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 C1,C2,,C(n)4 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 rG(C4) é

(n)4
∑         (n-)4
   μXi =   24 .
i=1
Observamos que o valor médio de Xi2 é o mesmo de Xi 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 Ci e Cj fixos, na segunda coluna temos a fração de grafos que contém esses Ci e Cj 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 rG(C4) 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 G(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 G(n), o seguinte fato é verdadeiro:

|        2|
||e(G )-  n-||< δn2
|       4 |
por menor que seja δ, se n é suficientemente grande.

Demonstração. Definimos e1,e2,⋅⋅⋅,eN 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:

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 lij é 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 é, ij:

           (
∑          |{ 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 = (v1,v2,,vn)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, vT Lv 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 = μ1 μ2 μn.

Exercício 94. Prove que se Δ(G) = d(v1) d(v2) d(vk) então μn d(v1) + d(v2).

Lema 95. A multiplicidade algébrica de μ1 é 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 μ1 é 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 μ1 t.

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

14.1 Autovalores da matriz laplaciana

Observação 96. Para grafos d-regulares, se L(G) é a matriz laplaciana com autovalores {μ1,n} e A(G) é a matriz de adjacência com autovalores {λ1,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 pA(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 μ1 μ2 μ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 μ1 μ2 μn os autovalores de L(G), então

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

Demonstração. Tome ei 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)