Uma rede de comunicação tem cinco locais com transmissores de potências distintas. Na matriz abaixo é definido , quando a i-ésima estação pode transmitir diretamente para a j-ésima estação, também temos quando a transmissão da i-ésima estação não alcança a j-ésima estação. Considere que . .
Calcule e dê o significado das matrizes A^2 e A+A^2.
Passo 1
O enunciado nos dá uma rede de comunicação com cinco estações e uma matriz de adjacência alcança diretamente a estação ,}\ 0,&caso contrário, \end{cases}]
e .
O conteúdo aqui é multiplicação de matrizes e interpretação de grafos: sabemos que o produto matricial conta o número de caminhos de comprimento 2 (dois saltos) de para .
Passo 2
Vamos calcular (A^2)ij=sumk=1^5 aikakj. Por exemplo, para i=1, j=4:
Significado de A^2: o elemento (A^2)ij é o número de maneiras distintas de ir da estação i à estação j em exatamente dois saltos (passando por alguma estação intermediária).
Passo 3
Agora somamos termo a termo A + A^2, que então contabiliza caminhos de comprimento 1 ou 2:
Significado de A + A^2: o elemento (A+A^2)ij dá o número total de caminhos da estação i à estação j que usam no máximo dois saltos (um ou dois). Se quisermos apenas saber se existe algum caminho com até dois saltos, bastaria olhar se (A+A^2)ij>0.