Algoritmos para Grafos, via Sedgewick | Índice remissivo

Grafos aleatórios

As funções que discutiremos abaixo constroem grafos 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 de 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->E < 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 minha página "Números aleatórios".) */
Vertex randV( Graph G) { 
   double r;
   r = rand( ) / (RAND_MAX + 1.0);
   return r * G->V;
}

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, pois GRAPHinsertE ignora as tentativas de inserir arestas "paralelas".

Exercícios 1

Na função randV, a expressão "rand()/(RAND_MAX+1.0)" pode ser trocada pela expressão "rand()/(RAND_MAX+1)"? E pela expressão "rand()/RAND_MAX"? E pela expressão "(float)rand()/RAND_MAX"?
Que acontece se randV for chamada com G->V maior que RAND_MAX+1?
Que acontece se a função GRAPHrand1 for chamada com E > V*(V-1)/2?
[Sedgewick 17.61, p.48] 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 2

Que acontece se a função GRAPHrand2 for chamada com E > V*(V-1)/2)? Que acontece se a função for invocada com V = 1?
[Sedgewick 17.69, p.49] Escreva uma programa que produza, com mesma probabilidade, cada um dos possíveis grafos com vértices 0..V-1 e (exatamente) E arestas.
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.)
[Sedgewick 17.73, p.49] 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.
[Sedgewick 17.90, p.62] 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.
[Sedgewick 17.71, p.49] 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.
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 GRAPHshow para exibir o grafo gerado.
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.)

Perguntas e respostas

Pergunta: Por que não usar a expressão r = rand( ) % V para gerar um número aleatório r no intervalo 0..V?
Resposta: Isso seria razoável se os números produzidos por rand fossem verdadeiramente aleatórios. Ocorre que esses números são apenas pseudoaleatórios e a única garantia que temos é que a função rand se esforça para produzir um número aleatório entre 0..RAND_MAX (no meu computador RAND_MAX vale 32767). Não há qualquer garantia de que os últimos dígitos do número gerado por rand sejam aleatórios (nem mesmo aproximadamente). Em particular, não há qualquer garantir de que o resto da divisão por V seja aleatório (nem mesmo aproximadamente).