Teoria dos Grafos
Período 2003.1

Representação de Grafos

Representação de Grafos

A representação gráfica que utilizamos é necessária para a rápida compreensão e utilização na definição dos conceitos básicos da teoria dos gráficos. De fato, na maioria das situações práticas, utilizamos esse tipo de representação. Esta representação gráfica, entratento, não é adequada para representar internamente (em um computador) dados sobre a estrutura de um grafo. É necessário uma representação que o computador possa entender.

Existem várias formas de representar um grafo $G = (V, E)$. Variações em termos de tamanho do grafo e de sua complexidade, propiciaram diversas formas de representação de um grafo. As mais conhecidas são:

1. Coleção de listas de adjacência.
2. Matriz de adjacência.
3. Matriz de incidência.

A representação com listas de adjacência é mais utilizada porque provê uma forma compacta de representar grafos esparsos , isto é, grafos onde $\vert E\vert$ é bem menos do que $\vert V\vert^2$.

A representação com matriz de adjacência é indicada no caso de grafos densos, onde $\vert E\vert$ é perto de $\vert V\vert^2$.

Listas de Adjacência

A representação com listas de adjacência de um grafo $G = (V, E)$ consiste de um array $Adj$ de $\vert V\vert$ listas, um para cada vértice de $V$. Para cada $u \in V$, a lista de adjacência $Adj[u]$ contém um ponteiro para todos os vértices $v$, onde existe um arco $(u, v) \in E$. Logo, $Adj[u]$ consiste de todos os vértices de $G$ que são adjacentes a $u$. Esses vértices são armazenados em ordem arbitrária.

A figura abaixo mostra um grafo não dirigido e sua representação com listas de adjacência.

Se $G$ é um grafo dirigido, a soma dos tamanhos de todas as listas de adjacências é $\vert E\vert$. A figura abaixo mostra um grafo dirigido e sua representação com listas de adjacência.

Em ambos os casos, grafos dirigidos ou não, a representação com listas de adjacÊncia possui uma propriedade desejável que indica que a quantidade de memória requerida é $O(max(V, E)) = O(V + E)$.

As listas de adjacência também pode ser utilizadas no caso de grafos ponderados e outras variantes de grafos.

A maior desvantagem desse método de representação é a de não possuir uma forma eficiente de dizer se um determinado arco $(u, v)$ está presente no grafo.

Matriz de Adjacência

A representação por matriz de adjacência de um grafo $G = (V, E)$ requer que os vértices sejam arbitrariamente numerados de $1, 2, ..., \vert V\vert$. A matriz de adjacência de um grafo de uma matriz $A = (a_{ij})$, de ordem $\vert V\vert \times \vert V\vert$, onde

$$\mbox{$a_{ij}$} = \left\{ \begin{array}{ll} 1 & \mbox{se $(i... ...\in E$} \\ 0 & \mbox{caso contrário} \end{array} \right.$$

A figura abaixo mostra um grafo não dirigido e sua representação com matriz de adjacência. Esse tipo de representação requer $O(V^2)$ de memória, independentemente do número de arcos do grafo.

Da mesma forma, a matriz de adjacência pode ser usada para representar grafos dirigidos.

Como na representação com listas de adjacência, a matriz de adjacência pode ser usada para representar grafos ponderados. Em vez de usar $1$ para indicar a presença do arco, utiliza-se o peso do arco.

Embora a representação com lista de adjacência seja pelo menos tão eficiente quanto a representação com matriz de adjacência, a simplicidade de uma matriz de adjacência a torna preferível no caso de grafos pequenos. No caso de grafos não ponderados, a representação com matriz de adjacência tem a vantagem de requerer apenas um bit por entrada.

Matriz de Incidência

A representação por matriz de adjacência de um grafo $G = (V, E)$ é uma matriz de dimensões $n \times m$, na qual cada linha corresponde a um vértice e cada coluna a uma aresta.

A matriz de incidência de um grafo (não dirigido), $A = (a_{ik})$, de ordem $\vert V\vert \times \vert E\vert$, onde

$\exists e_k = (i, j) \Leftrightarrow a_{ik} = a_{jk} = 1$. $a_{rk} = 0, \forall r \neq i, r \neq j$.

No caso de um grafo dirigido e sem laço, a matriz de incidência de um grafo, $A = (a_{ik})$, de ordem $\vert V\vert \times \vert E\vert$, onde

$\exists e_k = (i, j) \Leftrightarrow a_{ik} = +1$ e $a_{jk} = -1$. $a_{rk} = 0, \forall r \neq i, r \neq j$.