Diferença entre arestas cruzadas e arestas dianteiras em um DFT

11

Em uma primeira árvore de profundidade, existem as arestas que definem a árvore (ou seja, as arestas que foram usadas no percurso).

Existem algumas arestas restantes conectando alguns dos outros nós. Qual é a diferença entre uma aresta cruzada e uma aresta dianteira?

Da wikipedia:

Com base nessa árvore de abrangência, as arestas do gráfico original podem ser divididas em três classes: arestas dianteiras, que apontam de um nó da árvore para um de seus descendentes, arestas traseiras, que apontam de um nó para um de seus ancestrais, e bordas cruzadas, que não o fazem. Às vezes, as arestas das árvores, que pertencem à própria árvore de abrangência, são classificadas separadamente das arestas dianteiras. Se o gráfico original não for direcionado, todas as arestas serão arestas ou arestas traseiras.

Uma aresta que não é usada na travessia que aponta de um nó para outro estabelece um relacionamento pai-filho?

algorithms terminology graphs graph-traversal soandos
fonte
Relacionado: cs.stackexchange.com/questions/99988/… procura estabelecer um algoritmo que, para gráfico direcionado, prefira criar arestas diretas , em vez de arestas cruzadas, durante a pesquisa em profundidade.
Pfalcon

Respostas:

23

A Wikipedia tem a resposta:

insira a descrição da imagem aqui

Todos os tipos de arestas aparecem nesta imagem. Rastreie o DFS neste gráfico (os nós são explorados em ordem numérica) e veja onde sua intuição falha.


Isso explicará o diagrama: -

Borda dianteira: (u, v), em que v é um descendente de u, mas não uma borda de árvore. É uma borda que não é uma árvore que conecta um vértice a um descendente em uma árvore DFS.

Borda transversal: qualquer outra borda. Pode ir entre vértices na mesma árvore de profundidade primeiro ou em diferentes árvores de profundidade primeiro. (leigo)
É qualquer outra aresta no gráfico G. Ele conecta vértices em duas DFS-tree diferentes ou dois vértices na mesma DFS-tree, nenhum dos quais é o ancestral do outro.

Yuval Filmus
fonte
Por que não é impossível que 6 tenham sido percorridos primeiro (lado direito primeiro)? Se isso tivesse acontecido, como a borda 2-> 3 teria sido chamada?
soandos
@soandos, sugiro que você dedique algum tempo para rastrear o algoritmo. Supondo que os wikipedistas não cometeram um erro, a imagem descreve uma execução de boa fé do DFS neste gráfico e, portanto, existe uma maneira de ajustar o algoritmo nesse rastreamento. Os tipos de arestas são descritos com clareza suficiente na Wikipedia, e você também pode consultar este exemplo.
Yuval Filmus
Entendo que essa é uma maneira válida de fazer um DFS. Estou simplesmente perguntando o que foi feito de outra maneira.
soandos
Então os resultados seriam diferentes. Sinto muito, você teria que resolver isso sozinho.
Yuval Filmus
2
@soandos Em geral, pode muito bem haver várias travessias do DFS. As noções usadas aqui são relativas a uma determinada travessia e serão diferentes para travessias múltiplas.
Raphael
9

Uma travessia DFS em um gráfico não direcionado não deixará uma aresta cruzada, pois todas as arestas que são incidentes em um vértice são exploradas.

No entanto, em um gráfico direcionado, você pode encontrar uma aresta que leva a um vértice que foi descoberto antes, de modo que esse vértice não seja um ancestral ou descendente do vértice atual. Essa aresta é chamada de aresta cruzada.

Apoorv Gupta
fonte
Aporov, Obrigado pela resposta. Ainda me parece que, quando você chega ao vértice 6 no DFS, conforme diagramado na Wikipedia, você tem três arestas a partir do 6. Nesse ponto, o vértice 6 é "atual". Eventualmente, você atravessará a aresta até o vértice 3. Enquanto 3 já foi visitado, no entanto, como existe uma aresta de 6 a 3, 3 é um descendente do vértice "atual" 6. Se for assim, viola a definição de uma aresta cruzada. Deve haver algo mais na definição que não está sendo explicitado.
De fato, o DFS contém apenas as arestas da árvore para as arestas traseiras (Introdução aos algoritmos Thm. 22.10).
Jrhee17
2

Em uma travessia do DFS, os nós são concluídos quando todos os filhos são concluídos. Se você marcar os horários de descoberta e término de cada nó durante a travessia, poderá verificar se um nó é descendente comparando os horários de início e término. De fato, qualquer passagem do DFS particionará suas bordas de acordo com a regra a seguir.

Seja d [nó] o tempo de descoberta do nó, da mesma forma que f [nó] seja o tempo de término.

Teorema dos parênteses Para todos os u, v, exatamente um dos seguintes itens é válido:
1. d [u] <f [u] <d [v] <f [v] ou d [v] <f [v] <d [u ] <f [u] e nenhum de u e v é um descendente do outro.

  1. d [u] <d [v] <f [v] <f [u] e v é um descendente de u.

  2. d [v] <d [u] <f [u] <f [v] e u é um descendente de v.

Portanto, d [u] <d [v] <f [u] <f [v] não pode acontecer.
Como parênteses: () [], ([]) e [()] estão OK, mas ([)] e [(]) não estão OK.

Por exemplo, considere o gráfico com arestas:
A -> B
A -> C
B -> C

Deixe a ordem da visita ser representada por uma sequência de rótulos de nós, onde "ABCCBA" significa A -> B -> C (finalizado) B (finalizado) B (finalizado) A (finalizado), semelhante a ((())).

Portanto, "ACCBBA" pode ser um modelo para "(() ())".

Exemplos:
"CCABBA": Então A -> C é uma aresta cruzada, pois o CC não está dentro de A.
"ABCCBA": Então A -> C é uma aresta dianteira (descendente indireto).
"ACCBBA": Então A -> C é uma aresta de árvore (descendente direto).

Fontes:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

Chris Hafley
fonte