Uma rede de comunicação tem cinco locais com transmissores de potências distintas. Estabelecemos que ai j=1 na matriz abaixo, significa que a estação i pode transmitir diretamente a estação j e ai j=0 significa que a transmissão da estação i não alcança a estação j. Observe que a diagonal principal é nula, significando que uma estação não transmite diretamente a si mesma.
A=ccccc e1 & e2 & e3 & e4 & e5 [lllll 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 ] & & e1 & e2 & e3 & e4 & e5
(a) Construa um diagrama para representar as transmissões entre as estações, compatível com os dados da matriz A (disponha cada ei a uma certa distância uma da outra e ligue ei a ej conforme tenha transmissão ou não).
(b) Calcule A^2.
(c) Interprete o significado dos termos nulos, iguais a 1 e maiores que 1 , de modo a justificar a afirmação: " a matriz A^2 representa o número de caminhos disponíveis para se ir de uma estação a outra, com uma única transmissão intermediária".
(d) Qual o significado das matrizes A+A^2 ; A^3 e A+A^2+A^3 ?
(e) Calcule det A, mostrando que A^-1 não existe. Qual interpretação podemos dar para justificar a não existência de A^-1.
Uma ideia: Por exemplo, em A+A^2 o elemento c24=3, significa que existe um caminho de e2 à e4 sem transmissão intermediária (e2 e4) e mais dois caminhos com uma transmissão intermediária (e2 e3 e4) e (e2 e1 e4). Portanto, A+A^2 significa os caminhos disponíveis para cada estação transmitir a outra com nenhuma ou uma única transmissão intermediária.

Passo 1

O enunciado apresenta uma rede de comunicação com cinco estações e1,dots,e5 e a matriz de adjacência
A = 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
Conteúdo: teoria de grafos (matriz de adjacência) e caminhos de comprimentos variados. Precisaremos
  1. representar o grafo dirigido de A,
  2. calcular A^2 via multiplicação de matrizes,
  3. interpretar entradas de A^2,
  4. entender o significado de A+A^2, A^3, A+A^2+A^3,
  5. calcular det A e concluir sobre a inversibilidade de A.

Passo 2

(a) Para desenhar o diagrama, basta colocar cinco vértices rotulados e1,e2,e3,e4,e5 e, para cada par (i,j) tal que aij=1, traçar uma seta de ei para ej. Em particular:
– de e1 saem setas para e2,e3,e4,e5.
– de e2 saem setas para e1,e3,e4.
– de e3 saem setas para e2,e4.
– de e4 saem setas para e3,e5.
– de e5 sai uma seta apenas para e4.

Passo 3

(b) Usando l(A^2r)ij=sumk=1^5aik,akj, 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

Passo 4

(c) Cada entrada l(A^2r)ij conta o número de caminhos de comprimento 2 (duas transmissões) de ei a ej.
– Se l(A^2r)ij=0, não há caminho com exatamente uma estação intermediária.
– Se l(A^2r)ij=1, há exatamente um caminho de duas etapas.
– Se l(A^2r)ij>1, há múltiplos caminhos distintos passando por estações intermediárias diferentes.

Passo 5

(d)
A + A^2 tem (i,j)-ésimo termo igual ao número de caminhos de ei a ej usando 1 ou 2 transmissões (sem ou com uma estação intermediária).
A^3 conta o número de caminhos de 3 transmissões (duas estações intermediárias).
A + A^2 + A^3 apresenta todos os caminhos de até 3 transmissões entre as estações.

Passo 6

(e) Para det A expandimos por Laplace na primeira linha e achamos
det A ;=;-,det M12 ;+;det M13;-;det M14;+;det M15 ;=;-0 +(-1)-0 +1 ;=;0
Logo det A=0 e A^-1 não existe. Interpretação: como não há laços próprios ( aii=0) e nem conectividade que permita “desfazer” unicamente cada transmissão, a matriz de adjacência é singular e não admite inversa que recuperasse um único remetente para cada receptor.

Resposta

(a) Diagrama dirigido com vértices e1,dots,e5 e setas conforme a matriz A.
(b)
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
(c) Zero em l(A^2r)ij: nenhum caminho de duas transmissões; igual a 1: um caminho único; maior que 1: vários caminhos distintos.
(d) A+A^2 conta caminhos de até 2 transmissões; A^3 conta caminhos de 3 transmissões; A+A^2+A^3 conta caminhos de até 3 transmissões.
(e) det A=0, logo A^-1 não existe, refletindo que não há unicidade de “origem” em toda transmissão na rede.

Exercícios relacionados