Matriz de adjacência

Uma matriz de adjacência é uma das formas de se representar um grafo.

Dado um grafo G com n vértices, podemos representá-lo em uma matriz n x n A(G)=[a_ij] (ou simplesmente A). A definição precisa das entradas da matriz varia de acordo com as propriedades do grafo que se deseja representar, porém de forma geral o valor a_ij guarda informações sobre como os vértices v_i e v_j estão relacionados (isto é, informações sobre a adjacência de v_i e v_j).

Para representar um grafo não direcionado, simples e sem pesos nas arestas, basta que as entradas m_ij da matriz A contenham 1 se v_i e v_j são adjacentes e 0 caso contrário. Se as arestas do grafo tiverem pesos, a_ij pode conter, ao invés de 1 quando houver uma aresta entre v_i e v_j, o peso dessa mesma aresta.

Por exemplo, a matriz de adjacência do grafo ao lado é

$A={\begin{bmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{bmatrix}}$

Em grafos não direcionados, as matrizes de adjacência são simétricas ao longo da diagonal principal - isto é, a entrada a_ij é igual à entrada a_ji. Matrizes de adjacência de grafos direcionados, no entanto, não são assim. Num digrafo sem pesos, a entrada a_ij da matriz é 1 se há um arco de v_i para v_j e 0 caso contrário.

Um resultado interessante ocorre quando consideramos a potência k da matriz de adjacência, ou seja, o produto

{{A^{k}=} \atop {\ }}{{\underbrace {A\times \cdots \times A} } \atop k}.

Se A é a matriz de adjacência de um grafo G com conjunto de vértices dado por V(G)={v₁, v₂, ..., v_n}, então a entrada (i,j) de A^k, com k ≥ 1, corresponde ao número de caminhos (distintos) de comprimento k existentes entre os vértices v_i e v_j.

Pode-se mostrar esse resultado por indução. Quando k = 1, o resultado segue de modo natural da definição de matriz de adjacência, uma vez que existe um caminho de comprimento 1 entre o vértice v_i e o vértice v_j se e só se {v_i, v_j} é uma aresta de G. Seja

{A^{k-1}=\left[a_{ij}^{(k-1)}\right]},

e assuma que a_ij ^(k-1) é o número de caminhos distintos de comprimento k - 1 entre os vértices v_i e v_j em G. Considerando

{A^{k}=\left[a_{ij}^{(k)}\right]},

e como A^k = A^k-1 . A, temos que

{{a_{ij}^{(k)}=}{\sum _{p=1}^{n}a_{ip}^{(k-1)}a_{pj}}}.

Todo caminho entre v_i e v_j de comprimento k em G consiste de um caminho entre v_i e v_p de comprimento k - 1, onde v_p é adjacente a v_j, seguido da aresta {v_p, v_j} e do vértice v_j. O resultado decorre da hipótese de indução e da última equação.

Para digrafos, ...

Para ilustrar o resultado acima, observe as potências 2 e 3 da matriz de adjacência A correspondente ao grafo da figura. $A^{2}={\begin{bmatrix}3&2&1&1&2&0\\2&3&0&2&1&0\\1&0&2&0&2&1\\1&2&0&3&0&0\\2&1&2&0&3&1\\0&0&1&0&1&1\\\end{bmatrix}}$ ,