Re: [obm-l] Auto-valores de grafos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 18.08.04 22:01, Domingos Jr. at dopikas@uol.com.br wrote:

> Este aqui é bonitinho:
> Se G é um grafo d-regular com r componentes conexas e A é sua matriz de
> adjacência então A tem d como auto-valor de multiplicidade r.
> 
> [ ]'s
>
Vou supor inicialmente que o grafo eh conexo. O caso em que existem r
componentes conexas sai facilmente se considerarmos que A serah uma matriz
da forma diag(A_1,A_2,...,A_r), onde A_i eh a matriz de adjacencia da
i-esima componente conexa.

Pra ver que d eh um autovalor de A, basta tomar o vetor v = (1,1,...,1)^t e
fazer as contas. Voce vai achar que Av = dv.

Pra ver que d tem multiplicidade 1, considere um autovetor generico u =
(u_1,u_2,...,u_n)^t de A.
Seja u_j a componente de maior valor absoluto de u.
Entao a j-esima componente de Au serah igual a uma soma de d componentes u_i
e tambem serah igual a d*u_j (pois u eh autovetor de A associado a d).
Dada a escolha de u_j, isso soh poderah ocorrer se todos os u_i's forem
iguais, ou seja, u serah um multiplo escalar de (1,1,...,1)^t ==> o
auto-espaco de A associado ao autovalor d tem dimensao 1 ==>
d tem multiplicidade 1.

[]s,
Claudio.


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================