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

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 25.08.04 18:02, Domingos Jr. at dopikas@uol.com.br wrote:

> 
>> A coordenada (i, j) de B^k representa o número de passeios no grafo
>> (onde podemos repetir arestas) do vértice i até o vértice j.
>> Como o grafo é conexo, para algum k, B^k tem todas as entradas positivas.
> 
> faltou dizer que é o número de passeios no grafo com <= k arestas.
> =========================================================================

Eu acabei de ver um argumento simplerrimo:

Um vetor (x1,x2,...,xn)^t de R^n (n = numero de vertices do grafo G)
representa uma funcao F: V(G) -> R (ou seja, que associa um numero real a
cada vertice de G)

No nosso caso, com G sendo d-regular e conexo, um autovetor associado ao
autovalor d da matriz de adjacencia de G representa uma funcao F tal que,
para cada vertice v, adjacente a v1, v2, ..., vd, tenhamos:
F(v1) + ... + F(vd) = d*F(v) ==> F(v) = (F(v1) + ... + F(vd))/d

Seja w o vertice tal que F(w) eh maxima.
Entao, se os vertices w1, w2, ..., wd sao adjacentes a w, a condicao acima
implica que F(w) = F(w1) = ... = F(wd).

Agora, considere os vertices adjacentes a w1 (digamos u1, u2, ..., ud).
F(w1) = (F(u1) + ... + F(ud))/d = maximo ==>
F(u1) = ... = F(ud) = F(w1)

Prosseguindo dessa forma, dado que G eh conexo, concluimos que F eh
constante. Ou seja, (x1,...,xn)^t eh um multiplo escalar de (1,...,1)^t.

Isso significa que o autoespaco associado a d tem dimensao 1.

No entanto, sabe-se que a multiplicidade geometrica de um autovalor
(dimensao do auto-espaco associado) eh menor ou igual que a multiplicidade
algebrica (multiplicidade do autovalor como raiz do polinomio
caracteristico). Ou seja, pode ser que d seja uma raiz multipla do polinomio
caracteristico da matriz de adjacencia de G, apesar da sua multiplicidade
geometrica seja 1. Como provo que este nao eh o caso?

[]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
=========================================================================