Introdução aos Grafos

O que é isto

Um grafo modela relações de dois em dois. Cada objeto é um vértice (também chamado de nó) e cada relação é uma ligação entre dois vértices — o hipergrafo, definido mais abaixo, permite ligações com mais de dois extremos. Formalmente

onde $V$ é um conjunto finito não vazio de vértices e $E$ descreve as ligações.

A mesma notação $G=(V,E)$ serve para dois objetos. Em um grafo não dirigido, cada elemento de $E$ é um par não ordenado $\{u,v\}$: a aresta $\{u,v\}$ é a mesma que $\{v,u\}$. Em um grafo dirigido (digrafo), cada elemento de $E$ é um par ordenado $(u,v)$: o arco de $u$ para $v$. O arco $(u,v)$ não é o arco $(v,u)$; um pode existir sem o outro.

Por que dois tipos: relações simétricas (cabo de rede, rua de dois sentidos) pedem aresta-conjunto; relações de um lado só (hiperligação, pré-requisito, rua de mão única) pedem arco.

Dois vértices $u$ e $v$ são adjacentes se existe uma ligação entre eles. Um laço liga um vértice a si mesmo: $\{v,v\}$ no não dirigido, ou $(v,v)$ no dirigido.

Ideia central

Em um grafo simples, $E$ é um conjunto: no máximo uma aresta (ou um arco) com os mesmos extremos, e em geral sem laços. Se $E$ for conjunto, escrever $\{u,v\}$ duas vezes não cria duas arestas — é o mesmo elemento.

Em um multigrafo, $E$ é uma coleção: duas arestas não dirigidas podem ter os mesmos extremos, e dois arcos podem ter a mesma origem e o mesmo destino. Essas cópias chamam-se multiarestas (arestas paralelas).

Conjunto e coleção definem $E$ de formas diferentes. Se $E$ for conjunto, $\{u,v\}$ aparece no máximo uma vez: a segunda cópia é o mesmo elemento. Se $E$ for coleção, as duas cópias são arestas distintas — dois cabos entre os mesmos aparelhos, duas ruas paralelas entre os mesmos cruzamentos.

Exemplo mínimo: $V=\{u,v\}$ com duas arestas não dirigidas entre $u$ e $v$. Como conjunto, $E=\{\{u,v\}\}$ tem um elemento. Como coleção, $E$ tem dois. O desenho mostra duas linhas paralelas.

Arestas ponderadas carregam um número (custo, distância). Esta página usa só bits.

Para guardar $G$ no computador há duas representações clássicas. Fixe uma ordem $V = \{v_1,\ldots,v_n\}$, com $n = |V|$.

Matriz de adjacência de bits. A matriz $A$ — tabela retangular de entradas indexadas por linha e coluna — é $n \times n$. A entrada

se e somente se existe aresta (ou arco) de $v_i$ para $v_j$, e $A[i,j] = 0$ caso contrário.

No não dirigido, a aresta $\{v_i,v_j\}$ é um conjunto: liga $i$ a $j$ e $j$ a $i$. Por isso preenche as duas entradas $A[i,j]$ e $A[j,i]$ — a matriz é simétrica. No digrafo, $A[i,j]=1$ significa o arco $v_i \to v_j$; $A[j,i]$ é independente e pode ser $0$. Sem laços, a diagonal é $0$: $A[i,i]=1$ seria um arco (ou aresta) de $v_i$ para si mesmo.

A ordem dos rótulos é parte da representação: permutar $V$ permuta linhas e colunas. O grafo é o mesmo; a matriz muda. Sem uma ordem fixa, “a entrada $(2,3)$” não tem sentido — o $2$ e o $3$ são posições na ordem escolhida, não nomes intrínsecos.

A matriz de adjacência é $n \times n$, com $A[i,j]=1$ sse existe arco $i \to j$ — ou seja, se $i$ e $j$ são adjacentes nessa orientação. A matriz de incidência tem uma linha por vértice e uma coluna por aresta: a coluna da aresta $e$ marca os (dois) extremos de $e$.

Lista de adjacência. Para cada $v \in V$, guarda-se a lista dos vizinhos de $v$ — os vértices $w$ tais que existe aresta ou arco de $v$ para $w$. Seja $m = |E|$.

O espaço é proporcional a $n+m$ (na ordem de crescimento, $\Theta(n+m)$). Cada vértice contribui com um cabeçalho (mesmo que a lista seja vazia). Cada arco $(u,v)$ aparece só na lista de $u$. Cada aresta não dirigida $\{u,v\}$ aparece nas duas listas: $v$ na de $u$ e $u$ na de $v$. Por isso, no não dirigido, o número de apontadores é $2m$, não $m$.

Por que duas estruturas:

Grafo denso ($m$ da ordem de $n^2$): os espaços se aproximam; a matriz ganha na consulta pontual. Grafo esparso ($m$ linear em $n$): a lista economiza memória e a travessia custa da ordem de $n+m$, não de $n^2$.

Números: $n=100$, $m=200$. A matriz guarda $10\,000$ bits; a lista, cerca de $100$ cabeçalhos mais $400$ apontadores (aresta nas duas pontas). Com $m \approx n^2/2$ as duas ocupam a mesma ordem.

Três vértices, duas arestas

Sejam $V=\{A,B,C\}$ e arestas não dirigidas $E=\{\{A,B\},\{A,C\}\}$. Com linhas e colunas na ordem $A,B,C$, a matriz de bits $A$ começa nula: cada $1$ só entra quando uma aresta de $E$ o força.

Da matriz de bits ao digrafo

Dada a matriz $4 \times 4$ de bits abaixo, com vértices $\{1,2,3,4\}$ nessa ordem, reconstrua o digrafo: $A[i,j]=1$ se e somente se existe o arco $i \to j$.

Contagem na matriz de adjacências

No grafo não dirigido, a matriz de adjacências $A$ pode deixar de ser $0$-$1$: a entrada $A[i,j]$ é o número de arestas que ligam $v_i$ a $v_j$. A aresta $\{v_i,v_j\}$ coincide com $\{v_j,v_i\}$, logo $A[i,j]=A[j,i]$ — a matriz continua simétrica. Um laço em $v_i$ é aresta com os dois extremos em $v_i$, logo ocupa a diagonal: $A[i,i]$ conta os laços em $v_i$. Entradas podem ser inteiros maiores que $1$.

Por que inteiro e não bit: no multigrafo, duas arestas paralelas entre o mesmo par são objetos distintos. O bit $1$ colapsa as duas numa única presença; o inteiro $2$ preserva a multiplicidade. Peso é outra anotação: substitui o bit por um custo, não pela contagem de cópias.

Fixe $V=\{1,2,3\}$ nessa ordem, com duas arestas paralelas $\{1,2\}$, uma aresta $\{2,3\}$ e um laço em $3$.

Hipergrafo

No grafo ordinário cada aresta (ou arco) liga exatamente dois vértices. Um hipergrafo $H=(V,E)$ generaliza esse objeto: cada elemento de $E$ é uma hiperaresta, um subconjunto não vazio de $V$ com qualquer número de extremos — um vértice, dois, três ou mais. Não se exige que cada ligação tenha exatamente dois extremos.

No digrafo, cada arco tem dois extremos, só que ordenados: $(u,v)$ tem origem e destino. A direção não aumenta o número de extremos. Uma hiperaresta $\{u,v,w\}$ liga três vértices de uma vez; nenhum arco $(u,v)$ faz isso.

Por que a generalização: reuniões ou conjuntos que compartilham mais de dois elementos não cabem no modelo de pares. O grafo ordinário é o caso em que toda hiperaresta tem tamanho $2$.

Subgrafo

Um subgrafo de $G=(V,E)$ é um grafo $H=(V',E')$ tal que $V'\subseteq V$, $E'\subseteq E$, e cada aresta de $E'$ tem os extremos em $V'$. Não se inventa vértice nem aresta: só se escolhe um subconjunto de cada, respeitando a incidência.

Um laço é uma aresta $\{v,v\}$ (ou um arco $(v,v)$), não um subgrafo. O subgrafo é o par $(V',E')$, não uma ligação isolada.

O caso $V'=V$ e $E'\subseteq E$ é o subgrafo gerador: mesmos vértices, parte das arestas. A definição geral permite $V'$ próprio — pode-se largar vértices, desde que as arestas restantes não apontem para o que foi largado.