Matriz de adjacência

Matriz de Adjacência

Uma matriz de adjacências é 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 M. 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 m_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 M contenham 1 se v_i e v_j são adjacentes e 0 caso contrário. Se as arestas do grafo tiverem pesos, m_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, seja o grafo G(V, A) com vértices em V = {0, 1, 2, 3, 4} e arestas em A = {(0,0), (0,1), (0,2), (0,3), (2,3), (2,4)}. A matriz que representa esse grafo é

$M={\begin{bmatrix}1&1&1&1&0\\1&0&0&0&0\\1&0&0&1&1\\1&0&1&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 m_ij é igual à entrada m_jj. Matrizes de adjacência de grafos direcionados, no entanto, não são assim. Num digrafo sem pesos, a entrada m_ij da matriz é 1 se há um arco de v_i para v_j e 0 caso contrário.