Matriz de adjacência

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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)=[aij] (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 aij guarda informações sobre como os vértices vi e vj estão relacionados (isto é, informações sobre a adjacência de vi e vj).

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

6n-graph2.svg

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 aij é igual à entrada aji. Matrizes de adjacência de grafos direcionados, no entanto, não são assim. Num digrafo sem pesos, a entrada aij da matriz é 1 se há um arco de vi para vj 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 (v0, v1, ..., vi, ..., vk-1, vk) é tal que, para todo 0 ≤ i ≤ k-1, vi e vi+1 são vértices adjacentes. Os vértices v0 e vk são chamados, respectivamente, de origem e fim do percurso, enquanto v1, v2, ..., vk-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) = {v1, v2, ..., vn}, então a entrada (i,j) de Ak, com k ≥ 1, corresponde ao número de percursos (distintos) de comprimento k existentes entre os vértices vi e vj.

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 vi e o vértice vj se e só se {vi, vj} é uma aresta de G. Seja

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

e assuma que aij (k-1) é o número de percursos distintos de comprimento k - 1 entre os vértices vi e vj em G. Considerando

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

e como Ak = Ak-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 aij (k) é obtido multiplicando-se os elementos da linha i de Ak-1 pelos respectivos elementos da coluna j de A e, em seguida, efetuando-se a soma dos produtos obtidos.

Todo percurso entre vi e vj de comprimento k em G consiste de um percurso entre vi e vp de comprimento k - 1, onde vp é adjacente a vj, seguido da aresta {vp, vj} e do vértice vj. 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 A2 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 A3 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).

Bibliografia[editar | editar código-fonte]

  • CHARTRAND, G., LESNIAK, L. Graphs & Digraphs. Editora CRC Press, 2004.

Ver também[editar | editar código-fonte]

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.