Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Componentes de grafos

Esta página trata exclusivamente de grafo.  Em digrafos não simétricos, os conceitos correspondentes são mais complexos e serão discutidos 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

Eis um fato básico simples mas importante:  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, 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 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.

Componentes de grafos

Um conjunto X de vértices de um grafo G é fechado se

1. X não é vazio,
2. o subgrafo induzido por X é conexo  e
3. nenhuma aresta de G tem uma ponta em X e outra fora de X.

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 é um componente.  Assim, todo grafo tem uma coleção bem definida de componentes.

Exercícios

2. Mostre que duas componentes diferentes de um grafo não têm vértices em comum.
3. Determine o número de componentes do grafo definido pelo conjunto de arestas abaixo.

   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 lbl) 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 estão no mesmo componente.

#define maxV 10000
static int cc[maxV];

/* A função abaixo devolve o número de componentes do grafo G. Além disso, ela armazena no vetor cc o número do componente a que o vértice pertence: se o vértice v pertence ao k-ésimo 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 supõe que o grafo G é 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 no mesmo componente:

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

Exercícios

4. Prove que todo grafo conexo tem um vértice cuja remoção não desconecta o grafo. Escreva uma função que encontre um tal vértice. 
5. 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.
6. Faça experimentos para determinar quantas arestas um grafo aleatório com V vértices (para V = 100, 1000, 10000) precisa ter para ser conexo.  (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 um de seus componentes seja "gigante" (contenha, digamos, 0.95×V ou mais vértices).