Uma rede de comunicação tem cinco locais com transmissores de potências distintas. Na matriz A abaixo é definido ai j=1, quando a i-ésima estação pode transmitir diretamente para a j-ésima estação, também temos ai j=0 quando a transmissão da i-ésima estação não alcança a j-ésima estação. Considere que ai i=0.
A=[lllll0 & 1 & 1 & 1 & 1 1 & 0 & 1 & 1 & 0 0 & 1 & 0 & 1 & 0 0 & 0 & 1 & 0 & 1 0 & 0 & 0 & 1 & 0].
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:
(A^2)1,4 =sumk=1^5 a1kak4 = a12a24+a13a34+a14a44+a15a54 =1cdot1+1cdot1+1cdot0+1cdot1 =3
Fazendo o mesmo para todos os pares (i,j), obtemos
A^2 = 1 & 1 & 2 & 3 & 1 0 & 2 & 2 & 2 & 2 1 & 0 & 2 & 1 & 1 0 & 1 & 0 & 2 & 0 0 & 0 & 1 & 0 & 1
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:
A + A^2 = 0&1&1&1&1 1&0&1&1&0 0&1&0&1&0 0&0&1&0&1 0&0&0&1&0 + 1&1&2&3&1 0&2&2&2&2 1&0&2&1&1 0&1&0&2&0 0&0&1&0&1 = 1 & 2 & 3 & 4 & 2 1 & 2 & 3 & 3 & 2 1 & 1 & 2 & 2 & 1 0 & 1 & 1 & 2 & 1 0 & 0 & 1 & 1 & 1
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.

Resposta

A^2 = 1 & 1 & 2 & 3 & 1 0 & 2 & 2 & 2 & 2 1 & 0 & 2 & 1 & 1 0 & 1 & 0 & 2 & 0 0 & 0 & 1 & 0 & 1 , A + A^2 = 1 & 2 & 3 & 4 & 2 1 & 2 & 3 & 3 & 2 1 & 1 & 2 & 2 & 1 0 & 1 & 1 & 2 & 1 0 & 0 & 1 & 1 & 1
  • As entradas de A^2 contam caminhos de comprimento 2 entre as estações.
  • As entradas de A+A^2 contam caminhos de comprimento até 2 (isto é, de um ou dois saltos).

Exercícios relacionados