4. Propriedades Estruturais & Tempos de Descoberta
- O que significam os tempos de descoberta e finalização
- Por que os intervalos da DFS são estruturalmente importantes
- O teorema dos parênteses
- A intuição do teorema do caminho branco
- Relações de ancestralidade nas árvores DFS
- Por que essas propriedades são fundamentais para aplicações posteriores
A Busca em Profundidade é mais do que uma simples regra de travessia. Seus timestamps codificam uma estrutura oculta na exploração do grafo.
Nesta parte estudamos as propriedades formais dos tempos de descoberta, dos tempos de finalização e da estrutura de intervalos gerada pela recursão.
4.1 Tempos de Descoberta e Finalização
Durante a DFS, cada vértice u recebe dois timestamps:
- d[u] — momento em que u é descoberto
- f[u] — momento em que a exploração de u termina
Esses tempos satisfazem:
porque um vértice precisa ser descoberto antes de ser finalizado.
4.2 A Visão de Intervalos
Cada vértice define um intervalo de tempo:
Esse intervalo representa todo o período em que u está ativo na recursão.
O fato estrutural mais importante é que os intervalos da DFS são sempre **aninhados ou disjuntos**.
4.3 Teorema dos Parênteses
Para quaisquer dois vértices u e v, exatamente uma das situações ocorre:
- Os intervalos são disjuntos
- O intervalo de u contém o de v
- O intervalo de v contém o de u
4.4 Exemplo de Aninhamento
Isso significa que v é descendente de u.
4.5 Critério de Ancestralidade
Um vértice u é ancestral de v se e somente se:
4.6 Intervalos Disjuntos
Se dois vértices estão em ramos diferentes da DFS, seus intervalos são disjuntos.
4.7 Intuição do Caminho Branco
Um vértice v torna-se descendente de u se existir um caminho de vértices WHITE no momento em que u é descoberto.
4.8 Por que Isso Importa
- classificação de arestas
- detecção de ciclos
- ordenação topológica
- componentes fortemente conexas
Próximo: Parte 5 — Classificação de Arestas
Agora que entendemos os timestamps da DFS, podemos classificar as arestas do grafo.