1. Dizemos que um grafo G é fortemente ligado se para cada par de vértices há um caminho ligando eles. Como podemos testar se um grafo é fortemente ligado.

Passo 1

O enunciado pede verificar se um grafo dirigido G=(V,E) é fortemente ligado, ou seja, para cada par de vértices u,v existe caminho de u a v e de v a u. Vamos usar o algoritmo de Busca em Profundidade (DFS) e a construção do grafo transposto para fazer esse teste.

Passo 2

Escolhemos um vértice arbitrário rin V e executamos DFS em G a partir de r. Marcamos todos os vértices alcançados. Se existir algum vértice não marcado, concluímos que não há caminho de r até ele, logo G não é fortemente ligado.

Passo 3

Se todos os vértices forem alcançados, construímos o grafo transposto G^T=(V,E^T), onde
$$
E^T = {(v,u) : (u,v)\in E}\n$$
e executamos DFS em E^T = (v,u) : (u,v)in En a partir do mesmo vértice G^T. Novamente marcamos todos os vértices atingidos. Se houver algum não marcado, r não é fortemente ligado.

Passo 4

Se em ambas as buscas (em G e em G^T) alcançarmos todos os vértices, isso garante que existe caminho de r até qualquer v e também de v até r. Dessa forma, para qualquer par u,v há um caminho uto v e um caminho vto u, provando que G é fortemente ligado.

Resposta

Execute duas buscas em profundidade (DFS): uma em G e outra em seu grafo transposto G^T, ambas a partir de um mesmo vértice. Se em ambas as buscas você alcançar todo o conjunto de vértices V, então o grafo é fortemente ligado; caso contrário, não é.

Exercícios relacionados