domingo, 30 de outubro de 2016

Componentes conectados em Grafos

Em um grafo não-direcionado G, dois vértices u e v são ditos conectados se G contém um caminho de u para v. Senão, eles são chamados de desconectados.  Um grafo orientado (ou direcionado) é chamado de fracamente conectado se a substituição de todas as suas arestas direcionadas por arestas não direcionadas produz um grafo (não-direcionado) conectado. Ele é chamado de conectado se possui um caminho direcionado de u para v ou um caminho direcionado de v para u para cada par de vértices u, v. Ele é fortemente conexo se contém um caminho direto de u para v e um caminho direto v para u para cada par de vértices u, v. Um vértice de corte de um grafo conexo G é um conjunto de vértices que quando removidos torna G desconexo.

Um grafo não direcionado é conectado se cada par de vértices está conectado por um caminho. Os componentes conectados são as porções conectadas de um grafo. Um grafo não direcionado é conectado se ele tem exatamente um componente conectado.
Os componentes fortemente conexos são os subgrafos maximais fortemente conectados.
Os componentes fortemente conectados de um grafo direcionado são conjuntos de vértices sob a relação “são mutuamente alcançáveis”.

Por exemplo {0, 1, 2, 3}, {4} e {5} são os componentes fortemente conectados, {4, 5} não o é, pois o vértice 5 não é alcançável a partir do vértice 4.

O Algoritmo para achar estes componentes é:

  1. Aplicar a busca em profundidade no grafo G para obter os tempos de término t[u] para cada vértice u. 
  2. Obter o grafo G', que é o grafo transposto, isto é, são os mesmos vértices mas as arestas são invertidas. Assim existe uma arestas (u,v) em G' se existe uma aresta (v,u) em G. 
  3. Aplicar a busca em profundidade no grafo G' realizando a busca a partir do vértice de maior t[u] obtido na linha 1.
  4. Se a busca em profundidade não alcançar todos os vértices, inicie uma nova busca em profundidade a partir do vértice de maior t[u] dentre os vértices restantes.
  5. Retornar os vértices de cada árvore da floresta obtida na busca em profundidade na linha 3 como um componente fortemente conectado separado.