Considere o grafo

Encontre a matriz de adjacência A do grafo. (b) Calcule A2. O que os elementos da primeira linha de A2 lhe dizem sobre os caminhos de comprimento 2 que começam em Vi? (c) Calcule A'. Quantos caminhos de comprimento 3 existem de V2 a V4? Quantos caminhos de comprimento menor ou igual a 3 existem de V2 a V4?

Passo 1

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

  1. ‎Lembre-se que (i,j) entrada da matriz de adjacência representa uma linha nos vértices de beterraba grafia ‎ V i ‎ e ‎ V j ​‎. No caso de tal linha existir, a entrada é igual a 1. Caso contrário, é igual a 0. Além disso, já que a linha beterraba ‎ V i ‎ e ‎ V j ​‎ existe se e somente se a linha beterraba ‎ V j ​‎ e ‎ V i ​‎ existe, sabemos que a matriz de adjacência vai ser simétrica. Nenhum dos vértices está ligado a si mesmos. Assim, todas as entradas diagonais da matriz de adjacência são iguais a zero. Portanto, temos o seguinte:‎
  2. Passo 2

  3. Primeiro vamos calcular A 2
  4. ‎Sabemos que j-th entrada da primeira linha da matriz ‎ A 2 ‎ representa o número de caminhadas de comprimento 2 de ‎ V 1 ​‎ Para ‎ V j ​‎. Assim, podemos concluir que há 2 caminhadas de comprimento 2 de ‎ V 1 para ‎ V 1 1 caminhada de comprimento 2 de ‎ V 1 para cada um dos vértices restantes.‎

    Passo 3

  5. Aproveitando os resultados anteriores

A 3 = A 2 A

Sabemos que (2,4) entrada da matriz A k representa o número de caminhadas de comprimento k de V 2 a V 4 , para cada k = 1, 2, 3. Assim, podemos concluir que existem 5 caminhadas de comprimento 3 de V 2 a V 4 e 7 caminhadas de comprimento menor ou igual a 3 de V 2 a V 4 .

Resposta

Resposta nos passos.