Nos exercícios que perguntam "verdadeiro ou falso", deve-se justificar a resposta da seguinte forma: se for verdadeiro, com uma prova; se for falso, com um contra-exemplo.
*--------*-----* | |\ | | | \ | | | \| *--------* *
Significa o número de passeios que se consegue fazer de tamanho k, de i até j, sendo i, j E V.
Para entender melhor porque este é o significado, analise o que representa a posição (i, j) de A^2, onde A é a matriz de adjacência. Considere que o valor de a_i_j é e_i_j, igual a 1 se existe a aresta ij ou 0 caso esta aresta não exista. Então, o valor da posição (i, j) de A^2, denotada por a^2_i_j, é dado pela expressão:
a^2_i_j= e_i_1 * e_1_j + e_i_2 * e_2_j + ...+ e_i_n * e_n_j
Cada parcela e_i_p * e_p_j representa se existe um passeio de i para j passando por p, ou seja, um passeio de comprimento 2. Logo, a^2_i_j expressa o número de tais passeios.
Analogamente, considerando que em A^(k-1) o valor de a^(k-1)_i_j é e'_i_j, e este representa o número de passeios que se consegue fazer de tamanho (k-1), de i até j, então, o valor da posição (i, j) de A^k, denotada por a^k_i_j, é dado pela expressão:
a^k_i_j= e'_i_1 * e_1_j + e'_i_2 * e_2_j + ...+ e'_i_n * e_n_j
Cada parcela e'_i_p * e_p_j representa o número de passeios existentes de i para j de comprimento k que passam pela aresta (p, j). Logo, a^k_i_j expressa o número de passeios existentes de i para j, de comprimento k.