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.)