Cand inseram muchiile inainte nu apar triplete noi pentru care sa existe drum de la $A$ la $C$ si de la {$B$} la {$C$}, deci propozitia a fost demonstrata.

Arborele DF contine deci numai muchii de arbore si muchii inainte. Pentru un query {$(x y)$} vom aplica o strategie de tip greedy. Fie {$L$} = {$Lowest_Common_Ancestor(x, y)$}. Pentru a reorienta un numar minim de muchii, trebuie sa reorientam acele muchii care ne duc cat mai aproape de radacina. Astfel, trebuie sa ajungem intr-un nod {$u$}, stramos al lui {$x$}, pentru care {$nivel{~u~}$} ≤ {$nivel{~L~}$}. Daca putem ajunge din $x$ in {$u$}, putem cobori in arbore pana in {$y$}. Pentru acest pas vom folosi un algoritm liniar, de genul celui folosit in determinarea muchiilor critice in grafuri neorientate.
Fie {$low{~x~}$} nodul cel mai apropiat de radacina in care se poate ajunge din $x$ prin reorientarea a exact unei singure muchii si {$level{~x~}$} nivelul lui {$low{~x~}$}. Relatia de recurenta este:
 
{$level{~x~}$} = minim({$level{~parinte[x]~}$}; {$level{~y~}$} | y fiu al lui x; {$level{~u~}$} | {$u->x$} muchie inainte )
 
 
 

==Include(page="template/preoni-2007/footer")==