MAC0338   Análise de Algoritmos

Página preparada por Paulo Feofiloff para a disciplina MAC 338 Análise de Algoritmos, versão 1999.
O endereço original desta página é http://www.ime.usp.br/~pf/mac338/aulas/grafos.htm.

Grafos

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.

O que é um grafo?

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

Grafos na natureza

A natureza está cheia de grafos.  Eis alguns exemplos: 

• Cada vértice é um dos setores (agricultura, bancos, mineração, comércio, etc.) da economia de um país.  Há um arco de  x  a  y  se houver um fluxo significativo de bens e serviços de  x  para  y.  O grafo não tem arcos paralelos, mas pode ter laços; em geral, o grafo não é simétrico.
• Cada vértice é uma tarefa de um grande projeto.  Há um arco de  x  a  y  se  x  é pré-requisito de  y, ou seja, se  x  deve estar pronta antes que  y  possa começar.
• Cada vértice é um arquivo de um sistema de software.  Cada arco é uma "dependência":  um arquivo  v  é construído a partir de todos os arquivos  w  para os quais existe um arco da forma  (v,w). 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.
• Cada vértice é uma página na teia WWW.  Cada arco é um link que leva de uma página a outra.  [Parece que há cerca de 2 milhões de vértices e 5 milhões de arcos.]
• Os vértices são times de futebol e os arcos são os jogos entre os times durante um campeonato.  É claro que o grafo é simétrico e não tem laços (mas pode ter arcos paralelos).
• Cada vértice é uma espécie animal (cavalo, urso, koala, coelho, mosquito, etc. ) ou vegetal (cenoura, palmeira, eucalipto, alga, etc.).  Há um arco de  x  para  y  se a espécie  x  se alimenta da espécie  y. 
• Os vértices são as casas de um tabuleiro de xadrez.  Há um arco de  x  para  y  se um cavalo do jogo pode ir de  x  a  y  em um só movimento.  É claro que esse grafo é simétrico.
• Os vértices são palavras em português ("girafa", "girava", "cavalo", etc.).  Há um arco de  x  a  y  se e só se as duas palavras diferem em exatamente uma posição (por exemplo, há um arco de "girafa" a "girava").  É claro que o grafo não tem laços nem arcos paralelos, mas é simétrico.  (Poderíamos eliminar a simetria apagando o arco de  x  a  y  se  y  precede  x  no dicionário.) 
• Cada vértice do grafo é um conjunto com exatamente dois dos números  1, 2, 3, 4, 5.  Há um arco de  x  para  y  se os conjuntos são disjuntos.  Este grafo não tem laços nem arcos antiparalelos, mas é simétrico; ele é conhecido como grafo de Petersen.  (Poderíamos eliminar a simetria apagando o arco de  x  a  y  se  y  precede  x  na ordem lexicográfica.)
• Os vértices são intervalos (de tempo, por exemplo).  Há um arco de  J  para  K  (e também de  K  para  J) se os intervalos forem disjuntos.  É claro que esse grafo é simétrico.

Grafos no computador

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) é um arco.   (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ícios

1. Mostre que um grafo com n vértices tem no máximo n² arestas.
   
   
2. Escreva um algoritmo para verificar se (u,v) é uma aresta, ou seja, para verificar se v é adjacente a u.
   
   
3. Quanto espaço ocupa a representação de um grafo por meio de listas de adjacência?
   
   
4. [IMPORTANTE]  Considere o seguinte algoritmo que calcula o "grau de saída" g[u] de cada vértice u. O algoritmo supõe que os vértices do grafo são 1, 2,  . . . , n.

   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.
   
   

Grafos no SGB

O SGB representa internamente um grafo através de listas de adjacências.

Vértice (Vertex)

• arcs apontador para um Arc; e
• name apontador para uma cadeia de caracteres (string).

Se v aponta para um Vertex e v->arcs é NULL, então nào existem arcos saindo de v. Entretanto, se v->arcs não é NULL, ele aponta para uma estrutura do tipo arco Arc representando um arco de saindo de v, e esta estrutura Arc tem um campo next que aponta para o próximo arcos na lista ligada, encabeçada por v->arcs, de todos os arcos saindo de v.

Os campos para uso geral são chamados u, v, w, x, y, z. Macros podem ser usadas para dar a estes campos significado, dependendo da palicação.

  typedef struct vertex_struct {
    struct arc_struct *arcs; /* lista ligada de arcos saindo deste vértice */
    char *name; /* string identificando este vértice simbolicamente */
    util u, v, w, x, y, z; /* campos de uso geral */
  } Vertex;

Arco (Arc)

• tip: um apontador para um Vertex;
• next: um apontador para um Arc; e
• len: um inteiro (long).

Se a aponta par um Arc em uma lista de arcos saindo de v, ele representa um arco de comprimento a->len indo de v até a->tip, e o próximo arco saindo de v na lista é representado por a->next.

Os campos para uso geral são chamdos a e b.

  typedef struct arc_struct {
    struct vertex_struct *tip; /* o arco aponta pra este vértice */
    struct arc_struct *next; /* outro arco saindo do mesmo vértice */
    long len; /* comprimento do arco */
    util a,b; /* campos de uso geral */
  } Arc;
  

Grafo (Graph)

Uma estrutura do tipo Graph tem sete campos padrão e seis campos para uso geral. Os campos padrão são

• vertices: um apontador para um vetor de Vertex;
• n: o número total de vértices;
• m: o número total de arcos;
• id: um identificador simbólico;
• util_types: uma representação simbólica do tipo em cada campo para uso geral;
• data: aponta para a área usada para armazenar arcos e strings;
• aux_data: aponta para área usada para informação auxiliar.

Os campos para uso geral são uu, vv, ww, xx, yy, zz. Como uma conseqüência destas convenções, nós visitamos todos os arcos de um grafo g usando o seguinte trecho de programa:

  Vertex *v;
  Arc *a;

  for (v = g->vertices; v < g->vertices + g->n; v++)
    for (a=v->arcs; a; a= a->netx)
      visite(v,a);

typedef struct graph_struct {
  Vertex *vertices; /* começo do vertor de vértices */
  long n; /* número total de vértices */
  long m; /* número total de arcos */
  char id[ID_FIELD_SIZE]; /* Identificação do grafos */
  char util_types[15]; /* uso dos campos para uso geral */
  Area data; /* o bloco principal de dados */
  Area aux_data; /* blocos auxiliares  */
  util uu,vv,ww,xx,yy,zz; /* campos de uso geral */
} Graph;

Campos para uso geral (UTIL)

Os sufixos .V, .A, .G e .S no nome de uma variável de uso geral representa um apontador para um Vertex, Arc, Graph ou uma string, respectivamente; O sufixo .I significa que a variável é um inteiro (longo).

typedef union {
  struct vertex_struct *V; /* aponta para um Vertex */
  struct arc_struct *A; /* aponta para um Arc */
  struct graph_struct *G; /* aponta para um Graph */
  char *S; /* aponta para uma  string */
  long I; /* inteiro */
} util;

Campo util_types

"ZZZZZZZZZZZZZ"

Por exemplo, suponha que um grafo bipartido g usa o campo g->uu.I para guarda o tamanho da primeira das partições. Suponha ainda que g tem uma string em cada campo de uso geral a de cada Arc e usa o campo para uso geral w de cada Vertex para apontar para um Arc. Se g Não uso nenhum dos demais campos de uso geral então o seu util_types deve conter

"ZZAZZZSZIZZZZZ".

Módulo GB_GRAPH do SGB

Este módulo inclui rotinas para alocar e armazenar novos grafos, novos arcos, novas strings e novas struturas de dados de todos os tipos:

• Graph *gb_new_graph(long n).
  Um novo grafo é criado chamando-se gb_new_graph(n), que retorna um pointer para um registro do tipo Graph com n vértices e nenhum arco.
• void gb_new_arc(Vertex *u, Vertex *v, long len).
  Cria um novo arco de comprimento len de u até v. O arco passa a ser parte do grafo "corrente". O novo arco será apontado por u->arcs.
• void gb_new_edge(Vertex *u, Vertex *v, long len).
  Similar a gb_new_arc. Registros para dois arcos são criados, um de u a v e outro de v a u. Os dois arcos aparecem em posições consecutivas na memória: v->arcs é u->arcs + 1 quando u < v .
• char *gb_save_string (char *s).
  Faz uma cópia de s para ser usada no grafo "corrente".
• void gb_recycle (Graph *g).
  Remove o grafo apontado por g da memória.

Módulo GB_SAVE do SGB

Este módulo contém código para converter grafos da sua representação interna para uma representação simbólica e vice-versa:

• long save_graph (Graph *g, char *filename).
  Converte o grafo apontado por g para formato texto e salva o grafo no arquivo de nome filename.
• Graph *restore_graph (char *filename).
  Converte um grafo guardado no arquivo filename do formato texto para a representação interna dp SGB.

Passeios, caminhos, ciclos e circuitos

Um passeio em um grafo é uma seqüência de vértices em que cada dois vértices consecutivos são ligados por um arco. Mais exatamente, um passeio é uma seqüência 

<v₀,a₁,v₁,a₂,...,v_k-1,a_k,v_k> 

onde v₀, v₁,....,v_k são vértices, a₁,a₂,....,a_k são arcos e, para cada i, a_i é um arco de v_i-1 a v_i. O vértice v₀ é o início do passeio e o vértice v_k é o seu término.

Um caminho é um passeio sem vértices repetidos. Um ciclo é um passeio onde v₀ = v_k. Finalmente, um circuito é um ciclo sem vértices, com exceção feita a v₀ e v_k.

Exercícios

5. Problema: Dados vértices r e t de um grafo, decidir se existe um caminho de s a t. Mostre que o algoritmo guloso não resolve o problema.   [O algoritmo guloso pode ser resumido assim: Cada iteração começa com um caminho  (v₀,v₁,...,v_k-1,v_k)  tal que v₀ = s. Cada iteração consiste no seguinte: se v_k = t então pare. Senão, seja v_k+1 um vértice adjacente a v_k e comece nova iteração com o caminho (v₀,v₁,...,v_k-1,v_k,v_k+1).]
   
   

O território (ou domínio) de um vértice

Um vértice v é acessível a partir de um vértice r se existe um caminho de r a v. O território de um vértice r é o conjunto de todos os vértices acessíveis 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 um arco 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

Conexão

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.

Exercícios

6. Escreva um algoritmo que decida se um grafo é ou não fortemente conexo. Que coisa o algoritmo pode devolver para comprovar que o grafo é conexo? Que coisa pode devolver para comprovar que o grafo é desconexo?

Grafos simétricos

Um tipo muito comum e muito importante de grafo é o grafo simétrico. Um grafo é simétrico se para cada arco (u,v) existe também o arco (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.)

Exercícios

7. Escreva um algoritmo que decida se um grafo simétrico é ou não conexo. Que coisa o algoritmo pode devolver para comprovar que o grafo é conexo? Que coisa pode devolver para comprovar que o grafo é desconexo?
8. Escreva um algoritmo que recebe um grafo e decide se ele é simétrico. Qual o consumo de tempo do seu algoritmo?
9. (Versão mais difícil do exercício acima) Escreva um algoritmo que recebe um grafo e decide em tempo O(n+m) se ele é simétrico, onde n e m são o número de vértices e arcos do grafo, repectivamenete.