Diferencia entre bordes transversales y bordes delanteros en un DFT

11

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?

soandos
fuente
Relacionado: cs.stackexchange.com/questions/99988/… busca establecer un algoritmo que, para el gráfico dirigido, preferirá hacer bordes delanteros, en lugar de bordes cruzados, durante la búsqueda en profundidad.
pfalcon

Respuestas:

23

Wikipedia tiene la respuesta:

ingrese la descripción de la imagen aquí

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)

Yuval Filmus
fuente
¿Por qué no es imposible que 6 hayan sido atravesados ​​primero (primero el lado derecho)? Si eso hubiera sucedido, ¿cómo se habría llamado el borde 2-> 3?
soandos
@soandos, le sugiero que se tome el tiempo para rastrear el algoritmo. Suponiendo que los Wikipedia no cometieron un error, la imagen describe una ejecución de buena fe de DFS en este gráfico, por lo que hay una manera de ajustar el algoritmo en esta traza. Los tipos de bordes se describen con suficiente claridad en Wikipedia, y también puede consultar este ejemplo.
Yuval Filmus
Entiendo que esta es una forma válida de hacer un DFS. Simplemente estoy preguntando si se hizo de otra manera.
soandos
Entonces los resultados serían diferentes. Lo siento, tendrías que resolverlo tú mismo.
Yuval Filmus
2
@soandos En general, puede haber múltiples recorridos DFS. Las nociones utilizadas aquí son relativas a un recorrido dado y diferirán para múltiples recorridos.
Raphael
9

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.

Apoorv Gupta
fuente
Aporov, gracias por la respuesta. Todavía me parece que cuando llegas al vértice 6 en el DFS como se diagrama en Wikipedia, tienes tres bordes para atravesar desde 6. En ese punto, el vértice 6 es "actual". Eventualmente, va a atravesar el borde hasta el vértice 3. Si bien 3 ya se ha visitado, no obstante, dado que hay un borde de 6 a 3, entonces 3 es un descendiente del vértice "actual" 6. Si eso es así, viola La definición de un borde cruzado. Debe haber algo más en la definición que no se está haciendo muy explícito.
De hecho, DFS solo contiene los bordes de los árboles para los bordes posteriores (Introducción a los algoritmos Thm. 22.10).
jrhee17
2

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.

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

  2. 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

Chris Hafley
fuente