(UFF-RJ) Se representam 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 de A é igual ao número 1 se existe exatamente um voo direto da cidade para a cidade , caso contrário, esse elemento é igual ao número 0 . Uma propriedade importante do produto com , é 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
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.
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
Cálculo - Gelson Iezzi, Samuel Hazzan - Fundamentos de Matemática Elementar - Vol 4: Sequências, matrizes, determiantes e sistema - 8ª Edição - Capítulo Questões de Vestibulares.Questões de Vestibular - Ex. 150