# 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 a$_{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}.$
Antes de apresentar o resultado, vamos definir um percurso em um grafo G. Um percurso corresponde a uma sequência, finita e não vazia, de vértices do grafo, na qual (v$_0$, v$_1$, ..., v$_i$, ..., v$_{k-1}$, v$_k$) é tal que, para todo 0 ≤ i ≤ k-1, v$_i$ e v$_{i+1}$ são vértices adjacentes. Os vértices v$_0$ e v$_k$ são chamados, respectivamente, de origem e fim do percurso, enquanto v$_1$, v$_2$, ..., v$_{k-1}$ são os vértices internos ao caminho. O inteiro k é o comprimento do percurso. Um caminho em um digrafo é um percurso no qual todos os arcos estão orientados no sentido origem do percurso-fim do percurso.
Se A é a matriz de adjacência de um grafo G com conjunto de vértices dado por V(G) = {v$_1$, v$_2$, ..., v$_n$}, então a entrada (i,j) de A$^k$, com k ≥ 1, corresponde ao número de percursos (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 percurso 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 percursos 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}}}.$
Observe que, na expressão acima, o elemento a$_{ij}$ $^{(k)}$ é obtido multiplicando-se os elementos da linha i de A$^{k-1}$ pelos respectivos elementos da coluna j de A e, em seguida, efetuando-se a soma dos produtos obtidos.
Todo percurso entre v$_i$ e v$_j$ de comprimento k em G consiste de um percurso 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.
O resultado permanece válido para digrafos, fazendo-se as devidas adequações: trocando arestas por arcos e percursos por caminhos.
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}},A^{3}={\begin{bmatrix}7&6&3&3&6&1\\6&3&5&1&7&2\\3&5&0&5&1&0\\3&1&5&0&6&3\\6&7&1&6&3&0\\1&2&0&3&0&0\\\end{bmatrix}}$.
O elemento (4,6) de A$^2$ indica que não há nenhum caminho de comprimento 2 ligando os vértices 4 e 6 do grafo acima. Por outro lado, o elemento (4,6) de A$^3$ indica que existem 3 caminhos de comprimento 3 ligando os vértices 4 e 6. São eles: (4,3,4,6), (4,5,4,6) e (4,6,4,6).