Re: [obm-l] Auto-valores de grafos
Agora parece ok! = 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 =
Re: [obm-l] Auto-valores de grafos
on 26.08.04 11:42, Claudio Buffara at [EMAIL PROTECTED] wrote: > > 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? > Esquece! Isso eh consequencia do fato de a matriz de adjacencia ser simetrica. []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 =
Re: [obm-l] Auto-valores de grafos
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 =
Re: [obm-l] Auto-valores de grafos
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. = 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 =
Re: [obm-l] Auto-valores de grafos
Vamos mostrar o caso em que o grafo é conexo.
Considere a matriz B = A + I. Note que B é simétrica e real também.
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.
Agora note que se x não é múltiplo de (1, ..., 1) e Ax = dx, então Bx =
(d+1)x e, portanto x é auto-vetor de B.
Seja m tal que x_m é mínimo. Defina y = x - x_m*(1, ..., 1). Veja que y
é auto-vetor de B (com auto-valor correspondente d+1), cuja menor
coordenada é 0 e todas as demais são não-negativas.
B^k y = (d+1)^k y, mas isso é absurdo pois y_m = 0 e, portanto, [(d+1)^k
y]_m = 0, enquanto
[B^k y]_m > 0, pois este valor é a soma de valores não negativos (onde
pelo menos um valor é estritamente positivo).
Se o grafo tem r componentes conexas, podemos formar explicitamente uma
base de auto-vetores para a matriz de adjacência. Se há r componentes
conexas, digamos C_1, ..., C_r, então os vetores {v_i} que possuem 0 nas
coordenadas correspondentes a C_j com j != i e 1 nas coordenadas
correspondentes a C_i formam uma base de auto-vetores da matriz de
adjacência.
[ ]'s
=
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
=
Re: [obm-l] Auto-valores de grafos
on 24.08.04 16:38, Domingos Jr. at [EMAIL PROTECTED] wrote: > hmmm, lendo melhor o que vc escreveu, tem uma falha: > > "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..." > > > acontece que você descobriu que esses "d" u_i's são iguais, mas isso não > prova imediatamente que todos os u_i's são iguais... > eu tenho uma demonstração interessante, mas vou deixar você pensar um > pouco mais. > > [ ]'s > Verdade! Eu trabalhei com o exemplo de um grafo completo (para o qual o raciocinio estah correto) e nao atentei para este detalhe. A primeira ideia que me ocorreu foi tomar tambem a menor componente do autovetor associado a d. Como A eh simetrica e real, os seus autovalores sao reais e, portanto, os autovetores tem componentes reais. Seja v = (x_1,...,x_n)^t um autovetor associado a d e sejam x_r e x_s a menor e a maior componente de v, respectivamente. d*x_s = SOMA(i adjacente a s) x_i = x_i1 + ... + x_id e d*x_r = SOMA(j adjacente a s) x_j = x_j1 + ... + x_jd Logo, v deve ter pelo menos d+1 componentes iguais a x_r (incluindo x_r) e pelo menos d+1 componentes iguais a x_s (incluindo x_s). Isso prova o resultado para o caso em que n <= 2d+1, pois nesse caso os dois (multi)conjuntos de d+1 componentes se intersectam. Outra ideia que me ocorreu foi olhar para a matriz A - d*I. Fazendo a operacao elementar L_n <- L_1 + L_2 + ... + L_n (ou seja, somando cada uma das linhas a ultima linha dessa matriz) obtemos uma linha de zeros. Isso prova que A - d*I eh singular e, portanto, que d eh um autovalor de A. Se, alem disso, tivermos que posto(A - d*I) = n-1, entao acabou, pois nesse caso, nulidade(A - d*I) = dimensao do autoespaco associado a d = 1. Eu estou convencido de que isso eh verdade, mas nao consegui provar. Enfim, qual a sua solucao? []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 =
Re: [obm-l] Auto-valores de grafos
hmmm, lendo melhor o que vc escreveu, tem uma falha: "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..." acontece que você descobriu que esses "d" u_i's são iguais, mas isso não prova imediatamente que todos os u_i's são iguais... eu tenho uma demonstração interessante, mas vou deixar você pensar um pouco mais. [ ]'s = 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 =
Re: [obm-l] Auto-valores de grafos
Chicao Valadares wrote: eu gostaria que vc enviasse para mim.Estou estudando metodos probabilisticos e seria de grande utilidade. ok, eu ainda vou complementar mais a parte probabilística dessa monografia... a ênfase até o momento foi na parte construtiva. http://www.linux.ime.usp.br/~domingos/lb-ramsey.pdf opiniões são bem vindas. [ ]'s = 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 =
Re: [obm-l] Auto-valores de grafos
eu gostaria que vc enviasse para mim.Estou estudando metodos probabilisticos e seria de grande utilidade. --- "Domingos Jr." <[EMAIL PROTECTED]> escreveu: > perfeito! > > tem vários outros fatos interessantes que eu aprendi > recentemente na > minha iniciação científica. > estou escrevendo uma monografia pra participar da > jornada de IC no IMPA. > se você (ou mais alguém) tiver interesse em ver, eu > coloco na web. > > [ ]'s > = > 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 > = > = "O Binômio de Newton é tão belo como a Vênus de Milo. O que há é pouca gente para dar por isso... " Fernando Pessoa - Poesias de Alvaro Campos _ As informações existentes nessa mensagem e no(s) arquivo(s) anexado(s) são para uso restrito, sendo seu sigilo protegido por lei. Caso não seja destinatário, saiba que leitura, divulgação ou cópia são proibidas. Favor apagar as informações e notificar o remetente. O uso impróprio será tratado conforme as normas da empresa e a legislação em vigor. Agradecemos sua colaboração. The information mentioned in this message and in the archives attached are of restricted use, and its privacy is protected by law. If you are not the addressee, be aware that reading, disclosure or copy are forbidden. Please delete this information and notify the sender. Inappropriate use will be tracted according to company's rules and valid laws. Thank you for your cooperation. ___ Yahoo! Acesso Grátis - navegue de graça com conexão de qualidade! http://br.acesso.yahoo.com/ = 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 =
Re: [obm-l] Auto-valores de grafos
Hola mi nombre es Eduardo y soy un entrenador peruano, me interesa saber cuanto mas se pueda de lo que es grafos, especialmente la aplicacion en problemas de matematicas tipo de olimpiadas, te agradecere si me puedes enviar algun material, gracias."Domingos Jr." <[EMAIL PROTECTED]> wrote: perfeito!tem vários outros fatos interessantes que eu aprendi recentemente na minha iniciação científica.estou escrevendo uma monografia pra participar da jornada de IC no IMPA.se você (ou mais alguém) tiver interesse em ver, eu coloco na web.[ ]'s=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=Do You Yahoo!? Yahoo! Net: La mejor conexión a internet y 25MB extra a tu correo por $100 al mes.
Re: [obm-l] Auto-valores de grafos
perfeito! tem vários outros fatos interessantes que eu aprendi recentemente na minha iniciação científica. estou escrevendo uma monografia pra participar da jornada de IC no IMPA. se você (ou mais alguém) tiver interesse em ver, eu coloco na web. [ ]'s = 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 =
Re: [obm-l] Auto-valores de grafos
on 18.08.04 22:01, Domingos Jr. at [EMAIL PROTECTED] 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 =
