Considere a matriz

(a) Desenhe um grafo que tenha A como matriz de adjacência. Não se esqueça de marcar os vértices no gráfico.

(b) Analisando o grafo, determine o número de caminhos de comprimento 2 de V 2 , a V 3 e de V 2 , a V 5 .

(c) Calcule a segunda linha de A³ e use-a para determinar o número de caminhos de comprimento 3 de V 2 , a V 3 e de V 2 , a V 5 .

Passo 1

Saaaalve, tranquilo? Vamos lá resolver mais uma questão juntos?! 😊

‎a)

Lembre-se que a (i,j) entrada da matriz A representa uma linha beterraba entre os pontos ‎ V i ‎ e ‎ V j . O gráfico deve ser assim:‎

Passo 2

b) ‎A partir do vértice ‎ V 2 ‎ ​‎, há seguintes passeios de comprimento 1:‎

V 2 → V 1 , V 2 → V 3 , V 2 → V 4

‎No entanto, não há caminhadas de comprimento de 1 de ‎ V 1 ‎ ​,  V 4 ‎ ou ‎ V 3 ‎ para ‎ V 3 ​‎. Assim, não há caminhadas de comprimento de 2 de V 2 ​‎ para ‎ V 3 .

‎No entanto, não há caminhadas de comprimento de 1 de ‎ V 1 ​,  V 4 ou ‎ V 3 para ‎ V 3 ‎ . Assim, não há caminhadas de comprimento de 2 de ‎ V 2 para V 3

Passo 3

c) ‎Desde ‎ A 3 = A 2 A ‎, a fim de calcular a segunda linha da matriz ‎ A 3 ‎, só precisamos calcular a segunda linha de ‎ A 2 ‎ e multiplicá-lo com A. A fim de calcular a segunda linha de ‎ A 2 precisamos multiplicar a segunda linha da matriz A consigo mesma. Vamos denotar a segunda linha da matriz ‎ A 3 ‎ com ‎ x 2 ​‎ e a segunda linha da matriz A com a 2 ​‎. Nós temos o seguinte‎

‎Há 2 caminhadas de comprimento 3 de ‎ V 2 ​‎ para ‎ V 5

​.

Resposta

Resposta nos passos.