Strazi
Reformuland problema, trebuie sa adaugam un numar minim de muchii intr-un graf orientat aciclic astfel incat sa existe un drum hamiltonian. Un drum este o insiruire de noduri X1 X2 .. XK astfel incat sa existe o muchie intre oricare doua noduri consecutive. Printr-o acoperire cu drumuri a grafului vom defini o multime de drumuri astfel incat fiecare nod din graf apare exact intr-un singur drum. Daca multimea de drumuri are cardinalul minim, atunci acoperirea este minima. Sa presupunem acum ca am gasit o astfel de acoperire minima, multimea de drumuri fiind formata din drumurile D1, D2 .. DP.
Daca adaugam cate o muchie de la ultimul nod din drumul Di la primul nod din drumul Di+1 atunci graful nou format va contine un drum hamiltonian, deoarece toate nodurile din graf apar exact o singura data intr-un drum iar acum toate drumurile au fost unite. Este usor de vazut ca acesta este si numarul minim de muchii care trebuie adaugat (se demonstreaza usor prin reducere la absurd, daca ar exista un numar mai mic de muchii care ar putea fi adaugat atunci acoperirea cu drumuri obtinuta anterior nu ar mai fi minima). Sa ne concentram acum pe gasirea unei acoperiri minime. Vom construi un graf bipartit, in partea stanga vom pune nodurile de la 1 la N iar in partea dreapta de asemenea nodurile de la 1 la N. Sa alegem drumul D1 reprezentat prin succesiunea de noduri x1 x2 .. xt. Acest drum il vom reprezenta in graful bipartit astfel: vom trage muchie de la nodul x1 din partea stanga la nodul x2 din partea dreapta, de la nodul x2 din partea stanga la nodul x3 din partea dreapta etc. Vom face acelasi lucru pentru drumurile D2 .. DP si observam ca la sfarsit fiecare nod din graful bipartit are maxim un vecin. Mai mult, numarul de noduri din partea stanga din care nu pleaca nici o muchie este egal cu numarul de drumuri din acoperire. Pe noi ne intereseaza ca acest numar sa fie cat mai mic, deci trebuie sa existe un numar cat mai mic de noduri din partea stanga a grafului bipartit care nu au niciun vecin. Pentru a gasi acoperirea minima, pentru fiecare muchie x->y din graful initial vom plasa o muchie de la nodul x din partea stanga a grafului bipartit la nodul y din partea dreapta si vom rula un algoritm de cuplaj maxim. (cuplajul maxim ne garanteaza faptul ca am "cuplat" cat de multe noduri posibile din partea stanga a grafului bipartit)
