(UFF-RJ) Se C1, C2, ldots, Ck representam k cidades que compõem uma malha aérea, a matriz de adjacência associada à malha é a matriz A definida da seguinte maneira: o elemento na linha i e na coluna j de A é igual ao número 1 se existe exatamente um voo direto da cidade Ci para a cidade Cj, caso contrário, esse elemento é igual ao número 0 . Uma propriedade importante do produto com A^n=underbraceA A ldots An fatores , n in N, é a seguinte: o elemento na
linha i e na coluna j da matriz A^n dá o número de voos com exatamente n-1 escalas da cidade Ci para a cidade Cj.
Considere a malha aérea composta por quatro cidades, C1, C2, C3 e C4, cuja matriz de adjacência é:
A=[llll0 & 1 & 1 & 1 1 & 0 & 1 & 1 1 & 1 & 0 & 0 1 & 1 & 0 & 0]
Os números de voos com uma única escala de C3 para C1, de C3 para C2 e de C3 para C4 são, respectivamente, iguais a:
a) 0,0 e 1
b) 1,1 e 0
c) 1,1 e 2
d) 1,2 e 2
e) 2, 1 e 1

Passo 1

O enunciado dá a matriz de adjacência
A= 0 & 1 & 1 & 1 1 & 0 & 1 & 1 1 & 1 & 0 & 0 1 & 1 & 0 & 0
e pede o número de voos com exatamente uma escala (ou seja, dois trechos) de C3 para C1, C3 para C2 e C3 para C4. Como a entrada (i,j) de A^n conta o número de caminhos de comprimento n (aqui n=2 trechos =1 escala), basta calcular A^2.

Passo 2

Escrevemos a fórmula de multiplicação de matrizes para extrair a linha 3 de A^2:
(A^2)3j ;=;sumk=1^4 A3k,Akj
Como a linha 3 de A é (1,1,0,0), só entram na soma os dois primeiros termos.

Passo 3

Calculemos cada entrada:
(A^2)31 = 1cdot A11 + 1cdot A21 = 1cdot 0 + 1cdot 1 = 1,
(A^2)32 = 1cdot A12 + 1cdot A22 = 1cdot 1 + 1cdot 0 = 1,
(A^2)34 = 1cdot A14 + 1cdot A24 = 1cdot 1 + 1cdot 1 = 2

Passo 4

Portanto, o número de voos com uma única escala de
C3 para C1 é (A^2)31=1,
C3 para C2 é (A^2)32=1,
C3 para C4 é (A^2)34=2.

Resposta

c) 1, 1 e 2

Exercícios de Livros Relacionados