Vocês podem me ajudar com essa questão relacionado a Matrizes e Sistemas?
Valendo apenas nesse domingo (01/11/2020)
Soluções para a tarefa
Resposta: a)
__ l_V1__l l_V2__l l_V3__l l_V4__l l_V5__l
V1 l__0__l l__1__l l__0__l l__1__l l__0__l
V2 l__1__l l__0__l l__1__l l__1__l l__0__l
V3 l__0__l l__1__l l__0__l l__0__l l__0__l
V4 l__1__l l__1__l l__0__l l__0__l l__1__l
V5 l__0__l l__0__l l__0__l l__1__l l__0__l
b)
__ l_V1__l l_V2__l l_V3__l l_V4_l l_V5__l
V1 l__2__l l__1__l l__1__l l__1__l l__1__l
V2 l__1__l l__3__l l__0__l l__1__l l__1__l
V3 l__1__l l__0__l l__1__l l__1__l l__0__l
V4 l__1__l l__1__l l__1__l l__3__l l__0__l
V5 l__1__l l__1__l l__0__l l__0__l l__1__l
Partindo de v1 existem duas caminhos distintos, de distância 2, para se voltar até o próprio vértice v1.
c)
__ l_V1__l l_V2__l l_V3__l l_V4_l l_V5__l
V1 l__2__l l__4__l l__1__l l__4__l l__1__l
V2 l__4__l l__2__l l__3__l l__5__l l__1__l
V3 l__1__l l__3__l l__0__l l__1__l l__1__l
V4 l__4__l l__5__l l__1__l l__2__l l__3__l
V5 l__1__l l__1__l l__1__l l__3__l l__0__l
Partindo de v2 e indo até v4 temos 5 caminhos distintos de distância 3.
Existem 7 caminhos de v2 até v4 com d≤3.
Explicação passo-a-passo:
a) Temos que para montarmos uma matriz aij (sendo i suas linhas e j suas colunas) de adjacência de um grafo suas linhas e colunas serão formadas por vetores iguais e simétricos que representam todos os vértices. No caso ao lado teremos
__ l_V1__l l_V2__l l_V3__l l_V4_l l_V5__l
V1 l_.a11_l l_.a12_l l_.a31_l l_.a14_l l_.a15_l
V2 l_a21_l l_a22_l l_a23_l l_a24_l l_a25_l
V3 l_a31_l l_a32_l l_a33_l l_a34_l l_a35_l
V4 l_a41_l l_a42_l l_a43_l l_a44_l l_a45_l
V5 l_a51_l l_a52_l l_a53_l l_a54_l l_a55_l
Este tipo de matriz é preenchido inicialmente com o número de caminhos possíveis, com distância 1, do vértice i até o vértice j. Vamos começar preenchendo as ligações do vértice 1
__ l_V1__l l_V2__l l_V3__l l_V4_l l_V5__l
V1 l__0__l l__1__l l__0__l l__1__l l__0__l
V2 l__1__l l_____l l_____l l_____l l_____l
V3 l__0__l l_____l l_____l l_____l l_____l
V4 l__1__l l_____l l_____l l_____l l_____l
V5 l__0__l l_____l l_____l l_____l l_____l
Vamos agora preencher as outras relações
__ l_V1__l l_V2__l l_V3__l l_V4__l l_V5__l
V1 l__0__l l__1__l l__0__l l__1__l l__0__l
V2 l__1__l l__0__l l__1__l l__1__l l__0__l
V3 l__0__l l__1__l l__0__l l__0__l l__0__l
V4 l__1__l l__1__l l__0__l l__0__l l__1__l
V5 l__0__l l__0__l l__0__l l__1__l l__0__l
b) Temos que quando elevamos uma matriz ao quadrado cada um dos termos aij valerá agora a multiplicação da linha i pela coluna j. Tomemos como exemplo a11
a11² + a12*a21 + a13*a31 + a14*a41 + a15*a51
0² + 1*1 + 0*0 + 1*1 + 0*0
2
O mesmo será repetido para todos os outros 24 elementos até que obtenhamos a seguinte matriz
__ l_V1__l l_V2__l l_V3__l l_V4_l l_V5__l
V1 l__2__l l__1__l l__1__l l__1__l l__1__l
V2 l__1__l l__3__l l__0__l l__1__l l__1__l
V3 l__1__l l__0__l l__1__l l__1__l l__0__l
V4 l__1__l l__1__l l__1__l l__3__l l__0__l
V5 l__1__l l__1__l l__0__l l__0__l l__1__l
O que A² nos diz? Quantos caminhos diferentes, de distância 2, existem para se ir do vértice i até o vértice j. O que o elemento a11 nos diz sobre ele ser o único de valor 2? Que partindo de v1 existem duas caminhos distintos, de distância 2, para se voltar até o próprio vértice v1.
c) Para encontrarmos A³ repetiremos o processo anterior, só que agora multiplicando A²*A. Com isso encontraremos a seguinte matriz
__ l_V1__l l_V2__l l_V3__l l_V4_l l_V5__l
V1 l__2__l l__4__l l__1__l l__4__l l__1__l
V2 l__4__l l__2__l l__3__l l__5__l l__1__l
V3 l__1__l l__3__l l__0__l l__1__l l__1__l
V4 l__4__l l__5__l l__1__l l__2__l l__3__l
V5 l__1__l l__1__l l__1__l l__3__l l__0__l
Vemos, pela matriz, que partindo de v2 e indo até v4 temos 5 caminhos distintos de distância 3.
Portanto, o número de caminhos de v2 até v3 é:
1 de d = 1
1 de d = 2
5 de d = 3
1+1+5 = 7 caminhos
♥? ★★★★★? Melhor resposta? Você decide.
Bons estudos. ≧◉ᴥ◉≦
hm...