Olá pessoal da lista, quem puder me ajudar com esse problema.:
Numa matriz A,nxn, em que os elementos aij pode corresponder exclusivamente a 1 ou a 0, sendo que 1 indica ligação e 0 indica falta dessa(ligação) entre os vertices i e j, como eu faço para descobrir o menor caminho entre a e b, sendo estes pares ordenados de inteiros positivos, a<=n e b<=n.
Seja L = comprimento do caminho de a ate b:
Se a = b entao L = 0.
Se A(a,b) = 1 ==> L = 1 (a e b sao ligados por uma aresta)
Caso contrario, L = menor inteiro positivo n tal que o elemento (a,b) de A^n eh <> 0.
Ou seja, voce vai calculando potencias sucessivas de A = matriz de incidencia do seu grafo ateh que o elemento cujos indices correspondem ao seus dois vertices seja diferente de zero. O comprimento do seu caminho minimo serah justamente o expoente no qual isso acontece.
Um abraco,
Claudio.
Yahoo! Mail <http://br.mail.yahoo.com/>
O melhor e-mail gratuito da internet: 6MB de espaço, antivírus, acesso POP3, filtro contra spam.
Title: Re: [obm-l] Grafos
on 05.04.03 19:16, Jhonata Emerick at [EMAIL PROTECTED] wrote:
- [obm-l] Grafos David Ricardo
- Re: [obm-l] Grafos Johann Peter Gustav Lejeune Dirichlet
- Re: [obm-l] Grafos Carlos Yuzo Shine
- [obm-l] grafos Faelccmm
- [obm-l] Grafos Jhonata Emerick
- [obm-l] Grafos Claudio Buffara
- [obm-l] Grafos Jhonata Emerick