Exercício
de CLRS3 ou CLRS2 - Dê um algoritmo que determine se um dado grafo não dirigido
contém um ciclo simples. Esse algoritmo deve ser executado no tempo
, independentemente de
.
Passo 1
O enunciado pede: dado um grafo não dirigido
, decidir se
contém um ciclo simples. O algoritmo deve rodar em tempo
, independentemente de
.\n
Informações dadas (resumo claro):
Informações dadas (resumo claro):
- O grafo de entrada é
com vértices e arestas. - Queremos apenas responder “existe ciclo?” (sim/não).
- A restrição de tempo é que o tempo total seja
, sem depender de .
Observação: não estamos a pedir uma listagem de todos os ciclos, apenas a existência de pelo menos um ciclo simples.
Passo 2
Ideia-chave (observação combinatória simples que vai economizar tempo): um grafo sem ciclo é uma floresta (união de árvores). Numa árvore com
vértices o número de arestas é exatamente
. Para uma floresta com componentes cujos tamanhos em vértices são
temos que o número total de arestas satisfaz
onde
é o número de componentes conexas. Em particular
(pois
).\n
Portanto, conclusão lógica útil: se
Portanto, conclusão lógica útil: se
então o grafo não pode ser uma floresta e, portanto, necessariamente contém pelo menos um ciclo. Essa verificação usa apenas os valores
e
(que são parte natural da entrada).
Passo 3
Estratégia do algoritmo a partir da observação:
- Se
então responda “sim” (existe ciclo) imediatamente. Esse passo é . - Caso contrário, temos
. Então o número de arestas é menor que o número de vértices, logo . Nesse caso podemos executar um algoritmo padrão de busca (DFS ou BFS) que detecta ciclos em tempo ; como isso dá no pior caso — atendendo à restrição pedida.\n
Resumo da razão: o caso difícil (muito grande) é resolvido pela observação combinatória sem examinar arestas; o caso restante tem poucas arestas e permite exploração direta.
Passo 4
Detalhe didático: como detectar um ciclo com DFS em grafo não dirigido (passo necessário quando
).
- Estrutura de dados: vetor booleano
para cada vértice ; e ao fazer DFS guardamos também o vértice pai na árvore de busca. - Rotina DFS-visit(u):
- marque
. - para cada vizinho
de : - se
: coloque e chame DFS-visit( ). - senão (ou seja,
) e : então encontramos uma aresta que liga a um vértice já visitado que não é seu pai na árvore de busca — isso prova a existência de um ciclo simples; podemos parar e responder “sim”.
- se
- marque
- Explicação por que isso detecta um ciclo: em grafo não dirigido, toda aresta usada na árvore de busca tem seu outro extremo como pai/filho; se vemos uma aresta para um vértice já visitado que não é o pai, então existe um caminho simples entre
e na árvore de busca mais a aresta , formando um ciclo simples. - Observação prática: ao usar lista de adjacência, cada aresta aparece duas vezes (uma em cada lista), mas a análise de tempo padrão dá
.
Passo 5
Pseudocódigo final (em palavras e passos claros):
- Recebe
, com e . - Se
então retorne “sim” (existe ciclo) e termine. - Senão (isto é,
): - Inicialize
e para todo . - Para cada
: se faça DFS-visit( ) seguindo o procedimento do Passo 4; se algum DFS-visit detectar ciclo, retorne “sim”. - Se terminar todas as componentes sem detectar ciclo, retorne “não”.
Comentários sobre implementação: assuma que a entrada fornece também o valor(número total de arestas). Se o modelo de entrada não der explicitamente, pode-se passar pela lista de arestas uma vez para contar (isso custaria , o que violaria a restrição se for grande) — por isso a formulação do exercício normalmente permite acessar o valor sem varrer todas as arestas.
- Inicialize
Passo 6
Prova de corretude (resumida):
- Se
a observação do Passo 2 prova que o grafo não pode ser acíclico; então existe ciclo — correção imediata. - Se
: o algoritmo de DFS é conhecido por detectar ciclos em grafos não dirigidos: encontrar um vizinho já visitado que não seja o pai implica existência de ciclo; se não encontrarmos tal situação então o grafo é uma floresta (acyclic) e o algoritmo corretamente retorna “não”. Portanto o algoritmo está correto em ambos os casos.
Passo 7
Análise de complexidade detalhada:
- Verificação inicial
custa . - No caso
, o custo do DFS é . Como temos , portanto o custo é . - Logo, o tempo total do algoritmo é
no pior caso, independente de (pois quando é grande o algoritmo nem examina as arestas; quando é pequeno o DFS é linear em ).\n
Complexidade espacial padrão adicional épor conta dos vetores e .
Resposta
Se
então responda “sim” (existe ciclo). Caso contrário (isto é,
) execute uma busca em profundidade (DFS) que detecta aresta para vértice já visitado diferente do pai; se a DFS encontrar tal aresta responda “sim”, senão responda “não”. Este algoritmo roda em
.