Esta p�gina introduz os conceitos de grafo, caminho, e territ�rio (de um v�rtice). Ela serve de introdu��o a v�rios problemas (caminho m�nimo, �rvore geradora, ordena��o topol�gica, etc.) que estudaremos a seguir.
Um grafo � um objeto formado por dois conjuntos: um conjunto de v�rtices e um conjunto de arcos. Se V � o conjunto de v�rtices e A � o conjunto de arestas de um grafo, podemos dizer que o grafo � o par (V,A).
Cada arco corresponde a um par ordenado de v�rtices; o primeiro v�rtice do par � a ponta inicial do arco; o segundo v�rtice � a ponta final do arco. Um arco com ponta inicial u e ponta final v pode ser indicada por (u,v) ou ainda por uv. Algumas pessoas gostam de dizer "grafo orientado" ou "grafo dirigido", para enfatizar o car�ter orientado dos arcos.
Dizemos que um arco (u,v) sai do v�rtice u . Analogamente, um arco (u,v) entra em um v�rtice v. Dizemos tamb�m que um arco (u,v) vai de u a v.
Um grafo � sim�trico se para cada arco (u,v) existe um correspondente arco reverso (v,u). � comum, principalmente em livros de teoria das grafos, chamar um grafo sim�trico de "n�o-orientado" ou "n�o-dirigido" ou simplesmente de "grafo".
Um arco que tem a mesma ponta inicial e final � chamado dito um la�o (loop). Dois arcos que t�m a mesma forma, digamos (u,v) s�o chamados de paralelos.
Voc� pode imaginar que um grafo � uma esp�cie de mapa rodovi�rio: os v�rtices s�o cidades e as arestas s�o estradas de m�o �nica.
A natureza est� cheia de grafos. Eis alguns exemplos:
O grafo n�o tem arcos paralelos, mas pode ter la�os;
em geral, o grafo n�o � sim�trico.
Exemplo: se os arquivos s�o aaa.y, aaa.c, bbb.c, bbb.h, aaa.o, bbb.o, aaa e bbb, poderemos ter arcos da forma (aaa, aaa.o), (aaa.o, aaa.c), (aaa.o, bbb.h), etc.
O utilit�rio make do UNIX trabalha
sobre grafos deste tipo.
[Parece que h� cerca de 2 milh�es de v�rtices e 5 milh�es de arcos.]
Para especificar um grafo � preciso dizer quais s�o seus v�rtices e quais s�o suas arestas. � f�cil especificar os v�rtices: podemos dizer que eles s�o 1, 2, . . . , n. Mas como especificar as arestas?
Uma boa estrutura de dados para especificar as arestas � a matriz de adjac�ncia. Trata-se de uma matriz quadrada, digamos A, cujas linhas e colunas s�o indexadas pelos v�rtices. Para cada par u,v de v�rtices,
A[u,v] = 1 se existe aresta de u para v e
A[u,v] = 0 em caso contr�rio.
Uma outra estrutura de dados usada para especifica��o as arestas de um grafo � um conjunto de listas de adjac�ncias. Para cada v�rtice u temos uma lista linear
Adj[u] ,
implementada com ponteiros, que cont�m todos os v�rtices v tais que (u,v) � uma aresta. (A lista pode ter a seguinte estrutura. Cada n� da lista pode ter um campo vert e um campo prox. Se p � o endere�o de um n� ent�o vert[p] � o v�rtice armazenado no n� e prox[p] � o endere�o do pr�ximo n� da lista. Se p � o endere�o do �ltimo n� da lista ent�o prox[p] = NIL. O endere�o do primeiro n� da lista � Adj[u].)
EXERC�CIO (n, Adj)
para u := 1 at� n fa�a
g[u] := 0
para u := 1 at� n fa�a
para cada v em Adj[u] fa�a
g[u] := g[u]+1
devolva g
Mostre que esse algoritmo consome O(n+nm)
unidades de tempo, onde m � o n�mero de arestas.
Melhore esta estimativa, mostrando que
o algoritmo consome O(n+m)
unidades de tempo.
Um caminho em um grafo � uma seq��ncia de v�rtices em que cada dois v�rtices consecutivos s�o ligados por uma aresta. Mais exatamente, um caminho � uma seq��ncia
(v0,v1,...,vk-1,vk)
de v�rtices tal que, para todo i, o par (vi-1,vi) (n�o confunda (vi-1,vi) com (vi,vi-1)) � uma aresta. Um caminho � simples se n�o tem v�rtices repetidos.
Um v�rtice x � acess�vel a partir de um v�rtice r se existe um caminho de r a x. O territ�rio de um v�rtice r � o conjunto de todos os v�rtices a partir de r. O territ�rio de r ser� denotado por
X(r) .
Um v�rtice r � central se X(r) � o conjunto de todos os v�rtices do grafo. Um v�rtice � sorvedouro de X(r) = {r}.
PROBLEMA: Dado um v�rtice r de um grafo, encontrar o territ�rio de r.
A solu��o do problema ser� dada por um vetor cor indexado pelos v�ritices: para cada v�rtice u, teremos cor[u] = NEGRO se e s� se u est� no territ�rio de r. Um algoritmo guloso muito simples resolve o problema. No in�cio de cada itera��o temos duas classes de v�rtices, a classe dos v�rtices NEGROs e a classe dos BRANCOs. Todo v�rtice NEGRO est� no territ�rio de r. Cada itera��o escolhe uma aresta que vai de um v�rtice NEGRO a um v�rtice BRANCO e pinta esse �ltimo v�rtice de NEGRO.
Para administrar o processo, conv�m introduzir uma terceira cor, CINZA. O algoritmo abaixo sup�es que os v�rtices do grafo s�o 1, 2, . . . , n.
1
2
3
4
5
6
7
8
9
TERIT�RIO (n, Adj, r)
para u := 1 at� n fa�a
cor[u] := BRANCO
cor[r] := CINZA
enquanto existe u tal que cor[u] = CINZA fa�a
para cada v em Adj[u] fa�a
se cor[v] = BRANCO ent�o
cor[v] := CINZA
cor[u] := NEGRO
devolva cor
Um grafo � fortemente conexo se, para todo par r, s de seus v�rtices, existe um caminho de r a s e um caminho de s a r.
Em outras palavras, um grafo � fortemente conexo se e s� se X(s) = V para todo s.
Um tipo muito comum e muito importante de grafo � o grafo sim�trico. Um grafo � sim�trico se para cada aresta (u,v) existe tamb�m a aresta (v,u). Direi �s vezes que a aresta (v,u) � "g�mea" da aresta (u,v).
Se o grafo � representado no computador por meio de listas de adjac�ncia, digamos Adj, ent�o v est� em Adj[u] se e s� se u est� em Adj[v]. Se o grafo for representado por uma matriz de adjac�ncia, digamos A, ent�o A[u,v] = A[v,u] para todo par u, v.
Propriedade importante de grafos sim�tricos: existe caminho de r a s se e s� se existe caminho de s a r. Conseq��ncia: um grafo sim�trico � conexo se existe um v�rtice r tal que, para todo v�rtice v, h� um caminho de r a v. (Ou seja, um grafo sim�trico � conexo se tem um v�rtice central. E se tiver um v�rtice central ent�o todos s�o centrais.)