5. Classificação de Arestas
- Por que a DFS classifica arestas
- Os quatro tipos de arestas
- Arestas de árvore e estrutura da DFS
- Arestas de retorno e detecção de ciclos
- Arestas forward e cross
- Como os timestamps revelam os tipos de aresta
- Por que isso é importante para DAGs e análise de grafos
Uma vez que os timestamps da DFS estão disponíveis, as arestas deixam de ser apenas conexões no grafo. Elas passam a ter um significado estrutural em relação à floresta DFS.
5.1 Por que Classificar Arestas
A DFS atribui tempos de descoberta e finalização aos vértices, e esses tempos permitem interpretar cada aresta em relação à estrutura da busca.
Essa classificação é fundamental para:
- detecção de ciclos
- ordenação topológica
- análise de DAGs
- análise estrutural de grafos direcionados
5.2 Os Quatro Tipos de Arestas
| Tipo | Significado |
|---|---|
| Aresta de Árvore | A aresta descobre um novo vértice WHITE. |
| Aresta de Retorno | A aresta aponta para um ancestral na árvore DFS. |
| Aresta Forward | A aresta aponta para um descendente que não foi descoberto por ela. |
| Aresta Cross | A aresta conecta ramos diferentes da DFS. |
5.3 Arestas de Árvore
Uma aresta (u,v) é uma aresta de árvore quando v está WHITE no momento da exploração.
Essas arestas formam a estrutura da árvore DFS.
5.4 Arestas de Retorno
Uma aresta (u,v) é uma aresta de retorno quando aponta para um ancestral na árvore DFS.
5.5 Arestas Forward
Uma aresta forward conecta um vértice a um descendente na árvore DFS, mas não foi usada para descobri-lo.
5.6 Arestas Cross
Uma aresta cross conecta vértices que não possuem relação de ancestralidade na DFS.
5.7 Caracterização por Timestamps
Isso indica relação de ancestralidade.
5.8 Caso Especial: Grafos Não Direcionados
Em grafos não direcionados, existem apenas dois tipos de aresta:
- Arestas de árvore
- Arestas de retorno
5.9 Consequência para DAGs
Um grafo direcionado é acíclico se e somente se não houver arestas de retorno.