Diferencia entre bordes transversales y bordes delanteros en un DFT

En un primer árbol de profundidad, los bordes definen el árbol (es decir, los bordes que se usaron en el recorrido).

Hay algunos bordes sobrantes que conectan algunos de los otros nodos. ¿Cuál es la diferencia entre un borde cruzado y un borde delantero?

De wikipedia:

Según este árbol de expansión, los bordes del gráfico original se pueden dividir en tres clases: bordes delanteros, que apuntan desde un nodo del árbol a uno de sus descendientes, bordes posteriores, que apuntan desde un nodo a uno de sus antepasados, y bordes transversales, que tampoco lo hacen. A veces, los bordes de los árboles, que pertenecen al propio árbol de expansión, se clasifican por separado de los bordes delanteros. Si el gráfico original no está dirigido, todos sus bordes son bordes de árbol o bordes posteriores.

¿Un borde que no se usa en el recorrido que apunta de un nodo a otro no establece una relación padre-hijo?

Wikipedia tiene la respuesta:

Todos los tipos de bordes aparecen en esta imagen. Trace DFS en este gráfico (los nodos se exploran en orden numérico) y vea dónde falla su intuición.

Esto explicará el diagrama: -

Borde delantero: (u, v), donde v es un descendiente de u, pero no un borde de árbol. Es un borde que no es un árbol que conecta un vértice con un descendiente en un árbol DFS.

Borde cruzado: cualquier otro borde. Puede ir entre vértices en el mismo árbol primero en profundidad o en diferentes árboles primero en profundidad. (laico)
Es cualquier otra arista en el gráfico G. Conecta vértices en dos árboles DFS diferentes o dos vértices en el mismo árbol DFS, ninguno de los cuales es el antepasado del otro. (formal)

Un recorrido DFS en un gráfico no dirigido no dejará un borde cruzado ya que se exploran todos los bordes que inciden en un vértice.

Sin embargo, en un gráfico dirigido, puede encontrarse con un borde que conduce a un vértice que se ha descubierto antes, de modo que ese vértice no es un ancestro o descendiente del vértice actual. Tal borde se llama borde transversal.

En un recorrido DFS, los nodos se terminan una vez que todos sus hijos están terminados. Si marca los tiempos de descubrimiento y finalización para cada nodo durante el recorrido, puede verificar si un nodo es un descendiente comparando las horas de inicio y finalización. De hecho, cualquier recorrido DFS dividirá sus bordes de acuerdo con la siguiente regla.

Deje que d [nodo] sea el tiempo de descubrimiento del nodo, del mismo modo deje que f [nodo] sea el tiempo de finalización.

Teorema de paréntesis Para todos u, v, exactamente una de las siguientes afirmaciones:
1. d [u] <f [u] <d [v] <f [v] o d [v] <f [v] <d [u ] <f [u] y ninguno de u y v es descendiente del otro.

2. d [u] <d [v] <f [v] <f [u] yv es un descendiente de u.

3. d [v] <d [u] <f [u] <f [v] yu es descendiente de v.

Entonces, d [u] <d [v] <f [u] <f [v] no puede suceder.
Como paréntesis: () [], ([]) y [()] están bien pero ([)] y [(]) no están bien.

Por ejemplo, considere el gráfico con aristas:
A -> B
A -> C
B -> C

Deje que el orden de visita esté representado por una cadena de etiquetas de nodos, donde "ABCCBA" significa A -> B -> C (terminado) B (terminado) A (terminado), similar a ((())).

Entonces "ACCBBA" podría ser un modelo para "(() ())".

Ejemplos:
"CCABBA": Entonces A -> C es un borde cruzado, ya que el CC no está dentro de A.
"ABCCBA": Entonces A -> C es un borde delantero (descendiente indirecto).
"ACCBBA": Entonces A -> C es un borde de árbol (descendiente directo).

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