

	Determinarea numarului de piete si a pietii "26 martie 96" nu pun probleme deosebite.Dupa
aceasta, determinam inchiderea tranzitiva a grafului strazilor pentru a afla din ce intersectii
nu se poate ajunge in piata "26 martie 96".
	In scopul de a raspunde ultimei cerinte, incepem prin a determina graful condensat. Rea-
mintim ca graful condensat al unui graf este acel graf care are ca varfuri componenetele tare co-
nexe ale grafului initial, iar intre 2 componente tare conexe exista arc daca si numai daca in
graful initial exista un arc intre un varf al primei componente si un varf al celei de-a doua. O
proprietate importanta a grafului condensat este aceea de a fi aciclic.
	Observam ca nr. minim de arce care trebuie dublate in graful initial este egal cu nr. de
arce ce trebuie dublate in graful condensat. Vom schita in cele ce urmeaza demonstratia acestei
observatii.
	Intr-adevar, sa consideram mai intai o solutie optima in graful initial. Aceasta nu va pre-
supune dublarea unui arc intre 2 varfuri din aceeasi componenta tare conexa,deoarece nu ar schimba
cu nimic inchiderea tranzitiva a grafului. Din acelasi motiv, nu are rost diblarea a 2 arce intre
aceleasi 2 componente tare conexe. Transpunand acum dublarile de arce intre varfurile grafului
condensat, gasim o solutie pt. a face varful corespunzator pietei "26 martie 96" accesibil din
toate varfurile grafului condensat.
	Reciproc, data fiind o solutie pt. graful condensat, aceasta se va transpune in graful
initial.
	Facem o noua observatieL pt. a face accesibil varful corespunzator pietii "26 martie 96"
din toate varfurile grafului condensat este necesar si sufcient sa cobstruim drumuri pornind din
varfurile terminale (adica din care nu iese nici un arc) catre varful corespunzator pietei "26
martie 96" (drumurile amintite pot contine si arce deja existente).
	Din pacate, observatiile de mai sus duc doar la micsorarea dimensiunilor problemei,nu si
la gasirea unei solutii polinomiale. Aplicam in continuare metoda backtracking pt. graful condensat.
