on 25.08.04 18:02, Domingos Jr. at [EMAIL PROTECTED] 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 =========================================================================