- Dizemos que um grafo
é 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
é fortemente ligado, ou seja, para cada par de vértices
existe caminho de
a
e de
a
. 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
e executamos DFS em
a partir de
. Marcamos todos os vértices alcançados. Se existir algum vértice não marcado, concluímos que não há caminho de
até ele, logo
não é fortemente ligado.
Passo 3
Se todos os vértices forem alcançados, construímos o grafo transposto
, onde
$$
E^T = {(v,u) : (u,v)\in E}\n$$
e executamos DFS em a partir do mesmo vértice
. Novamente marcamos todos os vértices atingidos. Se houver algum não marcado,
não é fortemente ligado.
e executamos DFS em
Passo 4
Se em ambas as buscas (em
e em
) alcançarmos todos os vértices, isso garante que existe caminho de
até qualquer
e também de
até
. Dessa forma, para qualquer par
há um caminho
e um caminho
, provando que
é fortemente ligado.
Resposta
Execute duas buscas em profundidade (DFS): uma em
e outra em seu grafo transposto
, ambas a partir de um mesmo vértice. Se em ambas as buscas você alcançar todo o conjunto de vértices
, então o grafo é fortemente ligado; caso contrário, não é.