Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Grafos aleatórios

As funções que discutiremos abaixo constroem grafo aleatórios com vértices  0..V-1.  Poderíamos, igualmente bem, discutir a construção de digrafos (não simétricos) aleatórios, mas preferimos nos restringir aos grafos.

(Esta página é um resumo da seção 17.6 (Graph Generators) do capítulo 17 (Graph Properties and Types) do Sedgewick.)

Um gerador de grafos aleatórios

Nossa primeira função gera grafos aleatórios com exatamente E arestas. Do ponto vista do consumo de tempo, essa função não é muito apropriada para gerar grafos densos.

/* Para ter acesso à função rand e à constante RAND_MAX, preciso do arquivo-interface stdlib.h. */

#include <stdlib.h>

/* Gera grafo aleatório com vértices 0..V-1 e exatamente E arestas. (Código copiado do Programa 17.7, p.41, de Sedgewick.) */

Graph GRAPHrand1 (int V, int E) { 
   Graph G = GRAPHinit(V);
   while (G->A < 2*E) {
      Vertex v = randV(G);
      Vertex w = randV(G);
      GRAPHinsertE(G, v, w);
   }
   return G;
}

/* A função abaixo devolve um vértice aleatório do grafo G. (Embora Sedgewick não diga isso, o código só está realmente correto se G->V ≤ RAND_MAX+1. Veja a página "Números aleatórios".) */

Vertex randV (Graph G) { 
   return G->V * (rand() / (RAND_MAX + 1.0));
}

A função GRAPHrand1 só deve ser invocada com E bem menor que V*(V-1)/2.  À medida que E se aproxima desse limite, a execução da função consumirá cada vez mais tempo.

Exercícios

1. Que acontece se randV for chamada com G->V maior que RAND_MAX+1?
2. Que acontece se a função GRAPHrand1 for chamada com E > V*(V-1)/2)?
3. Quando usamos a função GRAPHrand1 para gerar grafos de grau médio  αV , que fração dos candidatos-a-aresta produzidos tem as duas pontas iguais?

Outro gerador de grafos aleatórios

A função abaixo gera grafos aleatórios que têm  E  arestas em média.

/* A função abaixo gera um grafo aleatório com vértices 0..V-1. Cada uma das V*(V-1)/2 possíveis arestas é gerada com probabilidade p, sendo p calculado de modo que o número esperado de arestas seja E (desde que E ≤ V*(V-1)/2). A função supõe que V ≥ 2. (Veja Sedgewick Program 17.8, p.42.) */

Graph GRAPHrand2 (int V, int E) { 
   Vertex v, w;
   double p = 2.0 * E / V / (V-1);
   Graph G = GRAPHinit(V);
   for (v = 0; v < V; v++)
      for (w = 0; w < v; w++)
         if (v != w && rand() <= p*RAND_MAX)
            GRAPHinsertE(G, v, w);
   return G;
}

Exercícios

4. Sedgewick escreve  "rand() < p*RAND_MAX"  onde eu escrevi  "rand() <= p*RAND_MAX".  Na prática, isso não faz diferença, mas eu acho que minha redação está mais correta. O que você acha?
5. Que acontece se a função GRAPHrand2 for chamada com E > V*(V-1)/2)?

Mais exercícios

6. Escreva uma programa que produza, com mesma probabilidade, cada um dos possíveis grafos com vértices 0..V-1 e (exatamente) E arestas.
7. Escreva uma função que gere um grafo com vértices 0..V-1 em que cada aresta v-w é escolhida aleatoriamente da seguinte maneira: primeiro, escolha v aleatoriamente em 0..V-1; depois, escolha w aleatoriamente no intervalo v-k..v+k, com v-k e v+k calculados módulo V.  (Veja figura 17.13, p.43, do Sedgewick.) 
8. Escreva uma programa que gere V pontos aleatórios no produto cartesiano de intervalos [0,1]×[0,1] e em seguida construa um grafo ligando por uma aresta os pontos que estejam à distância ≤ d um do outro. (Veja figura 17.12, p.41, do Sedgewick.)  Calcule d de modo que o número esperado de arestas seja E.
9. Determine empiricamente a probabilidade da existência de um caminho entre dois vértices escolhidos aleatoriamente em grafos aleatórios com V vértices e número esperado E de arestas.  Faça experimentos com diversos valores de V. Para cada V, tente determinar o valor de E a partir do qual a probabilidade de existir um caminho entre dois vértices aleatórios torna-se bastante alta.
10. Escreva uma função que receba inteiros n e E e gere um subgrafo aleatório de uma grade quadrada com n×n vértices.  Cada uma das arestas da grade deve ser incluída no grafo com probabilidade p, sendo p calculado de modo que o número esperado de arestas seja E.
11. Faça testes da função do exercício anterior. Sua função main deve aceitar valores de V e E na linha de comando e usar a função DIGRAPHshow para exibir o grafo gerado.
12. Escreva uma variante da função anterior que gere um subgrafo da grade descrito acima e acrescente a ele k arestas aleatoriamente escolhidas dentre as "diagonais" dos pequenos quadrados da grade. (Basta escolher aleatoriamente k "cantos superiores esquerdos" dos pequenos quadrados.)