* _Propozitie 1_: Arborele DF rezultat din parcurgerea de mai sus contine numai muchii de arbore sau muchii inainte.

Cum {$G*$} este aciclic, nu pot exista muchii de intoarcere ( inapoi ). Vom demonstra ca nu exista muchii transversale. Definim {$nivel{~x~}$} ca fiind numarul de noduri de la $x$ la radacina parcurgand numai muchii de arbore.
Presupunem prin reducere la absurd ca exista o muchie transversala {$x->y$}. Selectam acea muchie transversala {$x->y$} pentru care {$nivel{~y~}$} este minim. $Y$ nu poate fi radacina lui {$G*$}, pentru ca, in caz contrar, muchia {$x->y$} ar fi muchie de intoarcere si ar forma un ciclu, dar {$G*$} este aciclic. Deci exista un nod $u$ care este tatal lui {$y$}. Demonstram ca pentru tripletul {$(x u y)$} conditia (*) nu este indeplinita.
Exista drum de la $x$ la $y$ si de la $u$ la {$y$}. Drum de la $x$ la $u$ nu poate exista deoarece $u$ se afla in alt subarbore si, pentru a trece dintr-un subarbore in altul, trebuie se parcurgem muchii transversale. Dar {$x->y$} era muchia transversala pentru care {$nivel{~y~}$} era minim, si cum {$nivel{~u~}$} < {$nivel{~y~}$} si nu exista muchii de intoarcere => nu putem ajunge din $x$ in {$u$}. Nu putem ajunge nici din $u$ in $x$ datorita modului in care au fost sortate listele de adiacenta. Sa presupunem ca putem ajunge din {$u$} in {$x$}. Cum avem muchia {$x->y$}, $x$ apare inaintea lui $y$ in sortarea topologica, deci va aparea in listele de adiacenta mai devreme. Cand facem parcurgerea DF din nodul {$u$}, vom trece mai intai prin nodul $x$ si de abia dupa aceea prin nodul {$y$}, iar muchia {$x->y$} nu mai este muchie transversala.
Propozitia a fost demonstrata.

 
* _Propozitie 2_: Orice arbore DF care are doar muchii de arbore si muchii inainte indeplineste proprietatea (*).
 
 
Daca exista numai muchii de arbore si avem un triplet {$(A B C)$} care respecta ca exista drum de la $A$ la $C$ si de la $B$ la {$C$}, atunci si $A$ si $B$ se afla in lista predecesorilor lui C. Unul din nodurile $A$ sau $B$ trebuie sa apara primul in aceasta lista, deci vom avea drum fie de la $A$ la {$B$}, fie de la $B$ la {$A$}.
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.
 
 

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