Componentes de grafos

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.

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.

**Subgrafo Induzido: Um digrafo H é subdigrafo de um digrafo G se todo vértice de H é vértice de G e todo arco de H é arco de G.
Um subdigrafo de um digrafo G é próprio se for diferente de G.
Um subdigrafo de um digrafo G é gerador (= spanning) se contém todos os vértices de G.
Dado um conjunto X de vértices de um digrafo G, o subdigrafo de G induzido por X é o subdigrafo formado por X e por todos os arcos de G que têm ambas as pontas em X.
Um subdigrafo de um digrafo simétrico não é necessariamente simétrico. Portanto, um subdigrafo de um grafo não é necessariamente um grafo.
Um subgrafo (= subgraph) de um grafo G é qualquer grafo H que seja subdigrafo de G.

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 X1, X2, …, Xk em que cada Xi é um conjunto fechado. O subgrafo induzido por cada Xi é uma componente. Assim, todo grafo tem uma coleção bem definida de componentes.

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 para fazer o serviço.

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

int G[MAXV][MAXV]; //Grafo representado como Lista de adjacência
int grau[MAXV]; //Número de vértices adjacentes a cada vértice
int compconex[MAXV]; //Guarda a componente de cada vértice
int n; //Número total de vértices

/* 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 compconex[v] == k-1.*/

int Componentes(){ 

   int v; //vértice qualquer
   int id = 0; //id da componente atual

   memset(compconex,-1,sizeof(compconex)); //setando as componentes conexas

   for (v = 0; v < n; v++) //roda todos os vértices

      if (compconex[v] == -1)  //se ainda não tem componente, faz dfs

         dfsCompConex(v, id++); //dfs a partir de v e muda de componente (id++)

   return id; //retorna número de componentes
}

/* A função dfsCompConex supõe que o grafo G é representado por listas de adjacência. */

void dfsCompConex(int v, int id) { 

   int p; //indíce

   compconex[v] = id; //vértice v pertence a esta componente

   for (p = 0; p < grau[v]; ++p) //roda todos os adjacentes a v

      if (compconex[G[v][p]] == -1) //se ainda não tem componente

         dfsCompConex(G[v][p], id); //faz dfs a partir de G[v][p]

}

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

if(compconex[s] == compconex[t])
   printf("mesma componente");
else
   printf("componentes diferentes");

1. O que é um subgrafo induzido?
2. Todo grafo tem mais de uma componente conexa? Porque?
3. Faça o algoritmo dfsCompConex para um grafo representado por matriz de adjacências.
4. Defina a(s) componente(s) conexa(s) deste grafo: