Différence entre les bords croisés et les bords avant dans un DFT

Dans un premier arbre de profondeur, il y a les bords qui définissent l'arbre (c'est-à-dire les bords qui ont été utilisés dans la traversée).

Il y a des bords restants reliant certains des autres nœuds. Quelle est la différence entre un bord transversal et un bord avant?

De wikipedia:

Sur la base de cet arbre couvrant, les bords du graphique d'origine peuvent être divisés en trois classes: les bords avant, qui pointent d'un nœud de l'arbre vers l'un de ses descendants, les bords arrière, qui pointent d'un nœud vers l'un de ses ancêtres, et les bords croisés, qui ne font ni l'un ni l'autre. Parfois, les bords des arbres, les bords qui appartiennent à l'arbre couvrant lui-même, sont classés séparément des bords avant. Si le graphique d'origine n'est pas orienté, tous ses bords sont des bords d'arbre ou des bords arrière.

Un bord qui n'est pas utilisé dans la traversée qui pointe d'un nœud à un autre n'établit-il pas une relation parent-enfant?

Wikipédia a la réponse:

Tous les types de bords apparaissent sur cette image. Tracez DFS sur ce graphique (les nœuds sont explorés dans l'ordre numérique) et voyez où votre intuition échoue.

Cela expliquera le schéma: -

Bord avant: (u, v), où v est un descendant de u, mais pas un bord d'arbre. Il s'agit d'un bord non arborescent qui relie un sommet à un descendant dans un arbre DFS.

Bord transversal: tout autre bord. Peut aller entre les sommets dans le même arbre de profondeur d'abord ou dans différents arbres de profondeur d'abord. (profane)
Il s'agit de n'importe quelle autre arête du graphe G. Il relie des sommets dans deux arbres DFS différents ou deux sommets dans le même arbre DFS dont aucun n'est l'ancêtre de l'autre. (formel)

Une traversée DFS dans un graphe non orienté ne laissera pas de bord transversal, car tous les bords incidents sur un sommet sont explorés.

Cependant, dans un graphique dirigé, vous pouvez rencontrer une arête qui mène à un sommet qui a été découvert auparavant de telle sorte que ce sommet n'est pas un ancêtre ou un descendant du sommet actuel. Une telle arête est appelée arête transversale.

Dans une traversée DFS, les nœuds sont terminés une fois que tous leurs enfants sont terminés. Si vous marquez les heures de découverte et de fin pour chaque nœud pendant la traversée, vous pouvez vérifier si un nœud est un descendant en comparant les heures de début et de fin. En fait, toute traversée DFS partitionne ses bords selon la règle suivante.

Soit d [nœud] l'heure de découverte du nœud, de même f [nœud] l'heure de fin.

Théorème des parenthèses Pour tout u, v, exactement l'une des conditions suivantes:
1. d [u] <f [u] <d [v] <f [v] ou d [v] <f [v] <d [u ] <f [u] et aucun de u et v n'est un descendant de l'autre.

2. d [u] <d [v] <f [v] <f [u] et v est un descendant de u.

3. d [v] <d [u] <f [u] <f [v] et u est un descendant de v.

Donc, d [u] <d [v] <f [u] <f [v] ne peut pas se produire.
Comme les parenthèses: () [], ([]) et [()] sont OK mais ([)] et [(]) ne sont pas OK.

Par exemple, considérons le graphique avec des bords:
A -> B
A -> C
B -> C

Soit l'ordre de visite représenté par une chaîne d'étiquettes de nœuds, où "ABCCBA" signifie A -> B -> C (terminé) B (terminé) A (terminé), semblable à ((())).

Donc "ACCBBA" pourrait être un modèle pour "(() ())".

Exemples:
"CCABBA": Alors A -> C est un bord transversal, puisque le CC n'est pas à l'intérieur de A.
"ABCCBA": Alors A -> C est un bord avant (descendant indirect).
"ACCBBA": Alors A -> C est un bord d'arbre (descendant direct).

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