



		TRAMVAIE SI METROURI - SOLUTII
	       --------------------------------

1)	Se introduc linii de tramvai pe toate srazile, unde costul introducerii lor este mai
mic decat cel al neintroducerii lor. Se leaga apoi componentele conexe determinate de graficul
muchiilor de tramvai prin linii de metrou (daca este posibil). Daca nu se pot lega toate com-
ponenetele conexe prin linii de metrou, se vor lega cele ramase nelegate prin linii de tramvai,
astfel incat costul diferenta dintre costul actual si cel introducerii altor linii de tramvai
sa fie cat mai mica.

2)	Se introduc linii de tramvai pe toate strazile. Pe strazile unde costul introducerii
liniei de tramvai este mai mare decat costul neintroducerii ei, se scot liniile de tramvai ,daca
prin scoaterea lor componenta conexa careia ii aprtine muchia curenta nu se rupe in doua compo-
nente conexe. Daca muchia respectiva este "muchie critica" (prin scoaterea ei, componenta conexa
careia ii apartine devine neconexa), atunci se verifica daca cele 2 "jumatati" ale componenetei
conexe respective pot fi legate intre ele, sau cu alte componenete conexe. Daca nu se poate rea-
liza o astfel de legatura, atunci prin eliminarea muchiei curente, una din "jumatati" ar fi izo-
lata complet de restul grafului, si acesta nu ar putea fi conex -> muchia nu se elimina, si se
trece la urmatoarea muchie.