

		PROBLEMA SPONSORULUI - REZOLVARE
	       ----------------------------------

	Determinarea muchiilor critice se face adaptand algoritmul de determinare a componenetelor
biconexe prin parcurgerea DF a grafului. Anume, o muchie este muchie critica daca si numai daca
este muchie a arborelui DF si subarborele fiului nu are legaturi inapoi catre predecesori ai sai.
	Putem face o descompunere a grafului in componente fara punti (se numeste "punte" muchia
prin eliminarea careia graful devine neconex) si generam un nou graf in care varfurile corespund
componenetelor fara punti (adica subgrafurile maximale in sensul incluziunii multimilor ce nu
contin punti). Muchiile corespund puntilor dintre aceste componente (adica intre doua varfuri din
noul graf exista muchie daca si numai daca in graful initial exista o muchie intre un varf al
primei componente si un varf al celelilalte). Observam ca noul graf obtinut este un arbore si il
vom numi "arborele puntilor".
	Vom numi "noduri terminale" acele noduri ale arborelui puntilor care au un singur vecin.
Afirmam ca nr. minim de linii suplimentare este nt/2 daca nt este par, sau (nt+1)/2 daca nt este
numarul nodurilor terminale din arborele puntilor. Intr-adevar, acest numar nu poate fi micsorat,
deoarece fiecare nod terminal va trebui legat printr-o linie suplimentara de un alt nod. Acest
numar este suficient dupa cum vom vedea din urmatoarea metoda de constructie.

	Fie un arbore cu cel putin 4 noduri terminale. Fixam unul din nodurile terminale ca rada-
cina. Fie t1,t2,t3 alte 3 noduri terminale si a1,a2 respectiv a3 cel mai apropiat stramos comun
al varfurilor t1 si t2, t2 si t3, respectiv t3 si t1. Deoarece a1 si a2 sunt stramosi ai lui t2,
avem a1=a2, sau unul este stramos celuilalt; analog si pt. celelalte. In plus, nici unul dintre 
a1,a2,a3 nu este radacina, deoarece radacina are un singur descendent care ar fi si el stramos
comun.
	Distingem 2 cazuri:
a) a1,a2,a3 nu sunt toate egale. Presupunem ca a1 este stramos al lui a2, celelalte cazuri rezol-
vandu-se analog. Introducem o muchie intre varfurile t1 si t3 (adica intre varfuri ale componente-
lor atasate acestor varfuri). Noul arbore al puntilor astfel obtinut va avea 2 varfuri terminale
in minus. Intr-adevar, prin adaugarea muchiei (t1,t3) drumul (elementar) t1,...,a1,..,a2,..,t3,
devenit ciclu, se va reduce la un singur varf, neterminal, deoarece drumurile catre radacina si
catre t2 sunt diferite.
b) a1=a2=a3. In acest caz unim t1 cu t3 si aplicam acelasi rationament ca la a). 