Exercício 30 Considere a matriz de conexões entre três nós:
A=\left[\begin{array}{lll} 0 & 1 & 1 \\\\ 1 & 0 & 0 \\\\ 0 & 1 & 0 \end{array}\right]
(a) Calcule A^{2}.
(b) Interprete o significado das entradas de A^{2}.

Passo 1

O enunciado fornece a matriz de conexões entre três nós
A=\left[\begin{array}{ccc} 0 & 1 & 1 \\\\ 1 & 0 & 0 \\\\ 0 & 1 & 0 \end{array}\right]
e pede duas coisas:
  • (a) Calcular A^{2}.
  • (b) Interpretar o significado das entradas de A^{2}.
Informações relevantes dadas pelo enunciado:
  • A matriz A é uma matriz 3\times3 com elementos 0 ou 1.
  • Cada elemento A_{ij} indica uma conexão (aresta) do nó i para o nó j (valores iguais a 1 significam presença de aresta).

Passo 2

Fórmula que vamos usar para calcular A^{2}.
Quando multiplicamos matrizes, o elemento (i,j) da matriz produto A^{2}=A\cdot A é dado por
(A^{2})_{ij}=\sum_{k=1}^{3} A_{ik}\,A_{kj}.
Explicando cada parte:
  • (A^{2})_{ij} é a entrada na linha i e coluna j de A^{2}.
  • A_{ik} é o elemento da linha i e coluna k de A.
  • A_{kj} é o elemento da linha k e coluna j de A.
    Na prática isso significa: pegue a i-ésima linha de A e faça o produto escalar (dot product) com a j-ésima coluna de A.
Dica prática para prova: calcule cada (A^{2})_{ij} fazendo o produto escalar da linha i pela coluna j; como aqui os elementos são 0 ou 1, cada termo é simplesmente um produto 0 ou 1.

Passo 3

Vou escrever as linhas e colunas de A para facilitar os cálculos.
Linhas de A:
\text{linha 1}=(0,1,1),\qquad \text{linha 2}=(1,0,0),\qquad \text{linha 3}=(0,1,0).
Colunas de A:
\text{coluna 1}=(0,1,0)^{T},\qquad \text{coluna 2}=(1,0,1)^{T},\qquad \text{coluna 3}=(1,0,0)^{T}.
Agora calculamos cada entrada de A^{2} usando produto escalar.

Passo 4

Cálculos da primeira linha de A^{2} (ou seja, (A^{2})_{1j} para j=1,2,3):
(A^{2})_{11}=(0,1,1)\cdot(0,1,0)=0\cdot0+1\cdot1+1\cdot0=1.
(A^{2})_{12}=(0,1,1)\cdot(1,0,1)=0\cdot1+1\cdot0+1\cdot1=1.
(A^{2})_{13}=(0,1,1)\cdot(1,0,0)=0\cdot1+1\cdot0+1\cdot0=0.

Passo 5

Cálculos da segunda linha de A^{2} (ou seja, (A^{2})_{2j}):
(A^{2})_{21}=(1,0,0)\cdot(0,1,0)=1\cdot0+0\cdot1+0\cdot0=0.
(A^{2})_{22}=(1,0,0)\cdot(1,0,1)=1\cdot1+0\cdot0+0\cdot1=1.
(A^{2})_{23}=(1,0,0)\cdot(1,0,0)=1\cdot1+0\cdot0+0\cdot0=1.

Passo 6

Cálculos da terceira linha de A^{2} (ou seja, (A^{2})_{3j}):
(A^{2})_{31}=(0,1,0)\cdot(0,1,0)=0\cdot0+1\cdot1+0\cdot0=1.
(A^{2})_{32}=(0,1,0)\cdot(1,0,1)=0\cdot1+1\cdot0+0\cdot1=0.
(A^{2})_{33}=(0,1,0)\cdot(1,0,0)=0\cdot1+1\cdot0+0\cdot0=0.

Passo 7

Juntando todas as entradas calculadas, obtemos
A^{2}=\left[\begin{array}{ccc} 1 & 1 & 0 \\\\ 0 & 1 & 1 \\\\ 1 & 0 & 0 \end{array}\right].
Agora a interpretação das entradas: quando A é uma matriz de adjacência (conexões entre nós), o elemento (A^{2})_{ij} conta quantos caminhos de comprimento 2 (duas arestas) existem do nó i até o nó j. Por exemplo:
  • (A^{2})_{11}=1 significa que existe exatamente um caminho de comprimento 2 que sai do nó 1 e volta ao nó 1 (no caso é o caminho 1\to2\to1).
  • (A^{2})_{12}=1 significa que há exatamente um caminho de comprimento 2 de 1 até 2 (que é 1\to3\to2).
  • Entradas zero, como (A^{2})_{13}=0, significam que não existe nenhum caminho com exatamente duas arestas de 1 até 3.
Dica para a prova: para interpretar A^{k}, use a mesma ideia — (A^{k})_{ij} é o número de caminhos de comprimento k de i para j.

Resposta

(a) A^{2}=\left[\begin{array}{ccc} 1 & 1 & 0 \\\\ 0 & 1 & 1 \\\\ 1 & 0 & 0 \end{array}\right]
(b) As entradas (A^{2})_{ij} representam o número de caminhos de comprimento 2 (duas arestas) do nó i até o nó j.

Exercícios relacionados