Algoritmos para Grafos, via Sedgewick | Índice remissivo

Componentes de grafos

Esta página trata exclusivamente de grafos. Os conceitos correspondentes aos desta página para digrafos não simétricos são mais complexos e serão discutido em outra ocasião.

[Esta página corresponde a uma parte da seção 18.5 (DFS Algorithms), p.99-103, do capítulo 18 (Graph Search) do livro de Sedgewick.]

Grafos conexos e caminhos

Já dissemos que um grafo é conexo se não tem cortes vazios. Eis uma fato básico importante, que estabelece a relação entre essa definição e a existência de caminhos que ligam pares de vértices:

Fato: Um grafo é conexo se e somente se, para cada par (s,t) de seus vértices, existe um caminho com origem s e término t.

Em virtude da simetria dos grafos, a existência de um caminho de s a t equivale à existência de um caminho de t a s. Portanto, um grafo é conexo se e somente se quaisquer dois de seus vértices são ligados por um caminho.

Exercícios 1

Seja (s,t) um par de vértices de um grafo G sem cortes vazios. Prove que existe um caminho de s a t em G.
Suponha que todo par de vértices de um grafo G está ligado por um caminho. Prove que G não tem cortes vazios.
Seja s um vértice de um grafo. Suponha que todo vértice v do grafo é término de um caminho com origem s. Mostre que o grafo é conexo.
Seja G um grafo conexo com V vértices. Quantas são as arestas de G?
Escreva uma função GRAPHconnected que decida se um grafo é ou não conexo. (A função deve devolver 1 para indicar resposta afirmativa e 0 para indicar resposta negativa.) O que mais a função poderia devolver, além de 1 e 0, para provar que sua resposta está correta?
A função GRAPHconnected do exercício anterior é capaz de determinar se um digrafo é fracamente conexo? Por que?

Componentes de grafos

Uma componente de um grafo G é um tipo especial de subgrafo de G. Mais especificamente, é um tipo especial de subgrafo induzido de G. Nossa definição de componente começa com o conceito de conjunto fechado: um conjunto X de vértices de um grafo G é fechado se

X não é vazio,
o subgrafo induzido por X é conexo, e
o leque de X é vazio.

[A expressão conjunto fechado não é padrão. É apenas meu recurso didático para definir componentes.] Uma componente (= component) de um grafo é o subgrafo induzido por qualquer subconjunto fechado do seu conjunto de vértices. É claro que qualquer componente de um grafo é um grafo conexo. (A expressão "componente conexa" é às vezes usada no lugar de "componente".)

O conjunto de vértices de todo grafo admite uma única partição X₁, X₂, …, X_k em que cada X_i é um conjunto fechado. O subgrafo induzido por cada X_i é uma componente. Assim, todo grafo tem uma coleção bem definida de componentes. É claro que um grafo é conexo se e somente se tem uma só componente.

[Copiado das transparências de Sedgewick de 2006.]

Exercícios 2

Mostre que duas componentes diferentes de um grafo não têm vértices em comum.
[Sedgewick 17.4, p.15] Determine o número de componentes do grafo definido pelo conjunto de arestas a seguir.
```
     3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
```

Cálculo das componentes de grafos

A função abaixo calcula o número de componentes de um grafo. Ela usa uma busca em profundidade (com cc no papel de pre) para fazer o serviço.

Além de contar o número de componentes, a função atribui um rótulo cc[v] a cada vértice v de tal modo que dois vértices tenham o mesmo rótulo se e somente se estiverem na mesma componente.

#define maxV 1000
static int cc[maxV];
/* A função abaixo devolve o número de componentes do grafo G. Além disso, armazena no vetor cc o número da componente a que o vértice pertence: se o vértice v pertence à k-ésima componente então cc[v] == k-1. (O código foi copiado do programa 18.4, p.100, de Sedgewick.) */
int GRAPHcc( Graph G) { 
   Vertex v; int id = 0;
   for (v = 0; v < G->V; v++) 
      cc[v] = -1;
   for (v = 0; v < G->V; v++)
      if (cc[v] == -1) 
         dfsRcc( G, v, id++);
   return id;
}
/* A função dfsRcc marca com id todos os vértices que estão na mesma componente conexa que v. (Ou seja, faz cc[w] = id para todo w que esteja na mesma componente que v.) A função supõe que o grafo é representado por listas de adjacência. */
void dfsRcc( Graph G, Vertex v, int id) { 
   link p; 
   cc[v] = id;
   for (p = G->adj[v]; p != NULL; p = p->next)
      if (cc[p->w] == -1) 
         dfsRcc( G, p->w, id); 
}

Depois de executar GRAPHcc uma só vez, é possível saber, em tempo constante, se dois vértices, digamos s e t, estão na mesma componente:

    int GRAPHconnect( Graph G, Vertex s, Vertex t) { 
       return (cc[s] == cc[t]); 
    }

Exercícios 3

[Sedgewick 18.30, p.106] Prove que todo grafo conexo com dois ou mais vértices tem um vértice cuja remoção não desconecta o grafo. Escreva uma função que encontre um tal vértice.
[Sedgewick 18.31, p.106] Prove que todo grafo com dois ou mais vértices tem pelo menos dois vértices cuja remoção não aumenta o número de componentes.
[Sedgewick p.16] Seja G um grafo com V vértices e E arestas. Quantas componentes tem G no máximo? Quantas componentes tem G no mínimo?
[Sedgewick p.135] [Grafos aleatórios conexos] Faça experimentos para determinar quantas arestas um grafo aleatório com V vértices precisa ter para ser conexo. (Faça experimentos com V valendo 100, 1000, 10000.) Use a função GRAPHrand1 para gerar os grafos. Faça experimentos para determinar quantas arestas um grafo aleatório com V vértices precisa ter para que uma de suas componentes seja "gigante" (contenha, digamos, mais que 95% dos vértices). [Demonstra-se que quando o número de arestas passa de ½ V ln V (ou seja, pouco mais que V multiplicado pelo número de dígitos de V), o grafo consiste, com grande probabilidade, em uma componente "gigante" e alguns vértices isolados.]
[Evolução das componentes de grafos aleatórios] Escreva um programa para fazer uma série de experimentos. Cada experimento consiste em gerar um grafo aleatório com V vértices e E arestas e determinar o número de componentes, nc, e o tamanho tm de uma componente máxima. Para cada valor de V no conjunto {100, 1000, 10000}, faça os experimentos com E valendo 0.1V, 0.2V, 0.5V, 1, 2V, 5V e 10V. Repita cada experimento 10 vezes (variando a semente do gerador de números aleatórios) e tire a média dos valores de nc e a média dos valores de tm. [Demonstra-se que quando o número de arestas passa de ½ V ln V (ou seja, pouco mais que V multiplicado pelo número de dígitos de V), o grafo consiste, com grande probabilidade, em uma componente "gigante" e alguns vértices isolados.]
[Sedgewick-Wayne E.4.1.42, p.564] [Grafos euclidianos aleatórios conexos] Escreva uma função que gere grafos euclidianos aleatórios da seguinte maneira: primeiro, escolha V pontos aleatórios no quadrado [0,1]×[0,1]; depois, ligue dois pontos por uma aresta se a distância entre eles for ≤ d. Verifique experimentalmente que o grafo resultante é quase certamente conexo se d for maior que a raiz quadrada de (lg V)/(πV) e quase certamente desconexo se d for menor que esse número.
A função GRAPHcc é capaz de determinar se um digrafo é fracamente conexo?