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?! 😊
- Lembre-se que (i,j) entrada da matriz de adjacência representa uma linha nos vértices de beterraba grafia e . 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 e existe se e somente se a linha beterraba e 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:
- Primeiro vamos calcular
- Aproveitando os resultados anteriores
Passo 2
Sabemos que j-th entrada da primeira linha da matriz representa o número de caminhadas de comprimento 2 de Para . Assim, podemos concluir que há 2 caminhadas de comprimento 2 de para 1 caminhada de comprimento 2 de para cada um dos vértices restantes.
Passo 3
Sabemos que (2,4) entrada da matriz representa o número de caminhadas de comprimento k de a , para cada k = 1, 2, 3. Assim, podemos concluir que existem 5 caminhadas de comprimento 3 de a e 7 caminhadas de comprimento menor ou igual a 3 de a .
Resposta
Resposta nos passos.