g5i13io
Fie G = <X, V> un graf neorientat conex, unde X este multimea varfurilor si U este multimea muchiilor.Un arbore este un asemenea graf ce nu are cicluri. Fiecare muchie are un cost pozitiv (sau o lungime pozitiva). Pentru a gasi un arbore se pune problema sa gasim o submultime A inclusa in U, astfel incat toate varfurile din X sa ramina conectate atunci cand sunt folosite doar muchii din A.Numim arbore partial de cost minim acel arbore ce are multimea varfurilor X si a muchiilor A iar suma lungimilor muchiilor din A este minima.Cautam deci o submultime A de cost total minim care sa lege printr-un drum oricare doua noduri din X. Aceasta problema se mai numeste si problema conectarii oraselor cu cost minim, avand numeroase aplicatii.
Problema conectarii oraselor de cost minim:Se dau n orase precum si costul conectarii anumitor perechi de orase.Se cere sa se eleaga acele muchii care asigura existenta unui drum intre oricare doua orase astfel incat costul total sa fie minim.
Graful partial <X, A> este un arbore si este numit arborele partial de cost minim al grafului G (minimal spanning tree). Un graf poate avea mai multi arbori partiali de cost minim si acest lucru se poate verifica pe un exemplu.Vom prezenta doi algoritmi greedy care determina arborele partial de cost minim al unui graf. In terminologia metodei greedy, vom spune ca o multime de muchii este o solutie, daca constituie un arbore partial al grafului G, si este fezabila, daca nu contine cicluri. O multime fezabila de muchii este promitatoare, daca poate fi completata pentru a forma solutia optima. O muchie atinge o multime data de varfuri, daca exact un capat al muchiei este in multime. Urmatoarea proprietate va fi folosita pentru a demonstra corectitudinea celor doi algoritmi.
Multimea initiala a candidatilor este V. Cei doi algoritmi greedy aleg muchiile una cate una intr-o anumita ordine, aceasta ordine fiind specifica fiecarui algoritm.
1 Algoritmul lui Kruskal
Arborele partial de cost minim poate fi construit muchie cu muchie, dupa urmatoarea metoda a lui Kruskal (1956): se alege intai muchia de cost minim, iar apoi se adauga repetat muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu. Alegem astfel X-;1 muchii. Este usor de dedus ca obtinem in final un arbore. Este insa acesta chiar arborele partial de cost minim cautat?
Inainte de a raspunde la intrebare, sa consideram, de exemplu, graful din Figura 6.1.a. Ordonam crescator (in functie de cost) muchiile grafului: A1, 2S, A2, 3S, A4, 5S, A6, 7S, A1, 4S, A2, 5S, A4, 7S, A3, 5S, A2, 4S, A3, 6S, A5, 7S, A5, 6S si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 1.

Figura 1 Un graf si arborele sau partial de cost minim. Pasul Muchia considerata Componentele conexe alesubgrafului <X, A>
Initializare — A1S, A2S, A3S, A4S, A5S, A6S, A7S
1 A1, 2S A1, 2S, A3S, A4S, A5S, A6S, A7S
2 A2, 3S A1, 2, 3S, A4S, A5S, A6S, A7S
3 A4, 5S A1, 2, 3S, A4, 5S, A6S, A7S
4 A6, 7S A1, 2, 3S, A4, 5S, A6, 7S
5 A1, 4S A1, 2, 3, 4, 5S, A6, 7S
6 A2, 5S respinsa (formeaza ciclu)
7 A4, 7S A1, 2, 3, 4, 5, 6, 7S

Tabelul 1 Algoritmul lui Kruskal aplicat grafului din Figura1a.

Multimea A este initial vida si se completeaza pe parcurs cu muchii acceptate (care nu formeaza un ciclu cu muchiile deja existente in A). In final, multimea A va contine muchiile A1, 2S, A2, 3S, A4, 5S, A6, 7S, A1, 4S, A4, 7S. La fiecare pas, graful partial <X, A> formeaza o padure de componente conexe, obtinuta din padurea precedenta unind doua componente. Fiecare componenta conexa este la randul ei un arbore partial de cost minim pentru varfurile pe care le conecteaza. Initial, fiecare varf formeaza o componenta conexa. La sfarsit, vom avea o singura componenta conexa, care este arborele partial de cost minim cautat (Figura 1b).Ceea ce am observat in acest caz particular este valabil si pentru cazul general.
In vectorul V vom sorta in ordine crescatoare numarul muchiilor in ordine crescatoare in functie de costul fiecareia.In vectorul X vom retine pentru fiecare nod numarul componenetei din care face parte acesta si care se schimba o data ce adaugam o noua muchie.Modificarea acestuia se face in functie de apartenenta uneia dintre extremitati la un arbore cu mai mult de un nod.In multimea B se retin numerele de ordine ale muchiilor ce apartin arborelui de cost minim.

procedure sortare; Ase face sortarea intr-un vector v a muchiilor in ordine var i,k,min:integer; crescatoare a costurilor muchiilorS c:vector; begin c:=a;k:=0; repeat min:=maxint; for i:=1 to m do if (caii.cost<min) and (caii.cost<>0) then begin min:=caii.cost; j:=i; end; inc(k); vaki:=j; caji.cost:=0; until k=m; end; procedure kruskal; var i,k,j:integer; begin k:=0; for i:=1 to m do begin if (xaaavaiii.vf1i=0) and (xaaavaiii.vf2i=0) then Aambele extremitati begin formeaza un arbore cu un singur nodS b:=b+avaiii; inc(k); xaaavaiii.vf1i:=k; xaaavaiii.vf2i:=k; end else if xaaavaiii.vf1i<>xaaavaiii.vf2i then Ase verifica daca extremitatile begin muchiei sunt din arbori diferitiS b:=b+avaiii; if (xaaavaiii.vf1i<>0) and (xaaavaiii.vf2i<>0) then begin for j:=1 to n do if (xaji=xaaavaiii.vf1i) and (aavaiii.vf1<>j) then xaji:=xaaavaiii.vf2i; xaaavaiii.vf1i:=xaaavaiii.vf2i; end; if (xaaavaiii.vf1i=0) then xaaavaiii.vf1i:=xaaavaiii.vf2i; if (xaaavaiii.vf2i=0) then xaaavaiii.vf2i:=xaaavaiii.vf1i; end; suma:=suma+aavaiii.cost; end; end; begin AmainS clrscr; citire; for i:=1 to m do vaii:=0; sortare;
writeln('Vectorul sortat in ordinea muchiilor este:'); for i:=1 to m do
write(vaii,' ');
writeln; for i:=1 to n do xaii:=0; b:=ai; kruskal;
writeln('Muchiile arborelui sunt:'); suma:=0; for i:=1 to m do if i in b then begin
writeln('Muchia ',i,':',aaii.vf1,' ',aaii.vf2,' de cost ',aaii.cost); suma:=suma+aaii.cost; end;
write('Costul arborelui este:',suma); readkey; end.

2 Algoritmul lui Prim

Cel de-al doilea algoritm greedy pentru determinarea arborelui partial de cost minim al unui graf se datoreaza lui Prim (1957). In acest algoritm, la fiecare pas, multimea A de muchii alese impreuna cu multimea X a varfurilor pe care le conecteaza formeaza un arbore partial de cost minim pentru subgraful <X, A> al lui G. Initial, multimea W a varfurilor acestui arbore contine un singur varf oarecare din X, care va fi radacina, iar multimea A a muchiilor este vida. La fiecare pas, se alege o muchie de cost minim, care se adauga la arborele precedent, dand nastere unui nou arbore partial de cost minim (deci, exact una dintre extremitatile acestei muchii este un varf in arborele precedent). Arborele partial de cost minim creste “natural”, cu cate o ramura, pina cand va atinge toate varfurile din X, adica pina cand W = X. Functionarea algoritmului, pentru exemplul din Figura 6.1a, este ilustrata in Tabelul 2. La sfarsit, A va contine aceleasi muchii ca si in cazul algoritmului lui Kruskal.

Pasul Muchia considerata W
Initializare — A1S
1 A2, 1S A1, 2S
2 A3, 2S A1, 2, 3S
3 A4, 1S A1, 2, 3, 4S
4 A5, 4S A1, 2, 3, 4, 5S
5 A7, 4S A1, 2, 3, 4, 5, 6S
6 A6, 7S A1, 2, 3, 4, 5, 6, 7S

Tabelul 6.2 Algoritmul lui Prim aplicat grafului din Figura 6.1a.

Descrierea algoritmului este data in continuare.
Pentru a obtine o implementare simpla, presupunem ca: varfurile din X sunt numerotate de la 1 la n, X = A1, 2, ..., nS; matricea simetrica C da costul fiecarei muchii, cu Cai, ji = maxint, daca muchia Ai, jS nu exista. Folosim doi vectori,vectorul parintilor Taii si un vector saii.

Vectorul T este vectorul tata in care ,pentru fiecare nod i din X,Taii este egal cu parintele lui i.
Vectorul S este definit astfel:
Saii= 0 daca i apartine arborelui partial construit pana atunci
K daca :- i nu apartine arborelui partial deja construit
-muchia de cost minim care uneste i cu un nod din graful deja construit este ai,ki cu k neapartinand arborelui partial
Initial vectorul tata este 0 peste tot iar vectorul S este definit astfel:Savi=0 si Saii=v pentru i<>v,unde v este varful arborelui.Se alege apoi muchia de cost minim (i,j) care are numai o extremitate in arborele partial construit adica Saii=0 iar Saji<>0.Se reactualizeaza cei doi vectori:vectorul S pentru j adica Saji=0 iar vectorul tata Taji=Saji.Se reia cautarea muchiei de cost minim daca nu au fost alese n-1 muchii.

2 2 3

3
1 5 1
(a) 2 Figura 2 (b)
1 4
4
4
Aplicand acest algoritm pentru graful din Figura 2.a,se vor urma pasii:
-n=5,a matricea de cost si varful
-se alege varful,de exemplu v=1 iar vectorii sunt:
S
0 1 1 1 1
T
0 0 0 0 0
-si ia i=2,n si se alege muchia de cost minim determinata de aai,Saiii,(in acest caz se alege j=2).
-se reactualizeaza vectorii T si S;Taji=Saji(Ta2i=1) si S comparandu-se valoarea muchiei ai,Saiii cu cea a muchiei ai,ji si daca este mai mica se modifica S(Saii=j) unde Saii<>0 si j este ultimul varf introdus.Cei doi vectori vor fi:
S
0 0 2 2 1
T
0 1 0 0 0
-se cauta din nou muchia de cost minim si se repeta faza precedunta pana se aleg n-1 muchii(in cazul Figurii 2.a, 4 muchii).Vectorii vor suferii urmatoarele transformari:
1. S
0 0 4 0 1
T
0 1 0 2 0
. 2. S
0 0 4 0 0
T
0 1 0 2 1
3. S
0 0 0 0 0
T
0 1 4 2 1
-in final vectorul S va fi zero iar vectorul T va fi vectorul tata a arboreluipartial de cost minim.Costul arborelui(Figura 2.b) va fi 10.
Se cere sa se dea varful dar aceste poate fi luat intotdeauna 1 daca se cauta sa se afle numai costul arborelui deoarece,muchiile nefiind orientate, se obtine intotdeauna acelasi arbore.Cel ce difera este insa vectorul tata in funtie de varful de pornire dar acesta poate fi refacut dupa vectorul tata al grafului ce are varful 1.
Algoritmul lui Prim de determinare al arborelui partial de cost minim este: procedure prim; var i,j,min:integer; begin for i:=1 to n do saii:=v; savi:=0; for i:=1 to n do taii:=0; cost:=0; for k:=1 to n-1 do begin min:=maxint; for i:=1 to n do if (saii<>0) then if (aasaii,ii<min) and (aasaii,ii<>0) then begin min:=aasaii,ii; j:=i; end; taji:=saji; cost:=cost+aaj,sajii; saji:=0; for i:=1 to n do if (saii<>0) then if (aai,saiii=0) or (aai,saiii>aai,ji) then if aai,ji<>0 then saii:=j; end; end;
Bucla principala se executa de n-;1 ori si buclele for din interior necesita un timp in O(n). Algoritmul Prim necesita, deci, un timp in O(n2). Am vazut ca timpul pentru algoritmul lui Kruskal este in O(m log n). Pentru un graf dens (adica, cu foarte multe muchii), se deduce ca m se apropie de n(n-;1)/2. In acest caz, algoritmul Kruskal necesita un timp in O(n2 log n) si algoritmul Prim este probabil mai bun. Pentru un graf rar (adica, cu un numar foarte mic de muchii), m se apropie de n si algoritmul Kruskal necesita un timp in O(n log n), fiind probabil mai eficient decat algoritmul Prim.

Probleme propuse:

Problema 1.Se dau n orase.Se cunoaste distanta dintre oricare doua orase.Un distribuitor de carte cauta sa-si faca un depozit in unul dintre aceste orase.Se cere sa se gaseasca traseul optim de la depozit catre celelalte orase astfel incat distanta totala pe care o va parcurge pentru a distribui in toate celelalte n-1 orase sa fie minima.sa se precizeze care ar fi orasul in care sa se afle depoitul pentru ca toate celelalte orase sa fie usor accesibileAdin acel centru de depozitare sa se poata pleca sper cat mai multe alte oraseS.
Date se citesc dintr-un fisier astfel:
-pe prima linie numarul de orase

-pe urmatoarele linii traseele existente astfel:orasul din care pleaca,orasul in care ajunge si distanta in km a drumului.
ADeoarece vor exista foarte multe trasee algoritmul lui Prim este mai bun.Fiind un graf neorientat se poate pleca cu varful 1.Pentru a afla care ar fi orasul optim vedem inarbore care este nodul cu cei mai multi fii si refacem vectorul tata.S
Rezolvare: program oras_depozit; uses crt; type muchie=record vf1,vf2,cost:integer; end; type vector=arraya1..100i of longint; vector1=arraya1..100i of muchie; matrice=arraya1..50,1..50i of longint; var n,i,j,k,v,cost:integer; s,t:vector; x:vector1; a:matrice; f:text; procedure citire; var i,j,m:integer; begin assign(f,'depozit.txt'); reset(f); readln(f,n);m:=0;
while not eof(f) do begin inc(m); read(f,xami.vf1); read(f,xami.vf2); read(f,xami.cost); readln(f); end; for i:=1 to m do begin aaxaii.vf1,xaii.vf2i:=xaii.cost; aaxaii.vf2,xaii.vf1i:=xaii.cost; end;
writeln('Matricea costurilor este:'); for i:=1 to n do begin for j:=1 to n do
write(aai,ji,' ');
writeln; end; end; procedure prim; var i,j,min:integer; begin for i:=1 to n do saii:=v; savi:=0; for i:=1 to n do taii:=0; cost:=0; for k:=1 to n-1 do begin min:=maxint; for i:=1 to n do if (saii<>0) then if (aasaii,ii<min) and (aasaii,ii<>0) then begin min:=aasaii,ii; j:=i; end; taji:=saji; cost:=cost+aaj,sajii; saji:=0; for i:=1 to n do if (saii<>0) then if (aai,saiii=0) or (aai,saiii>aai,ji) then if aai,ji<>0 then saii:=j; end; end; function fii(x:integer):integer; var k:integer; begin k:=0; for i:=1 to n do if taii=x then inc(k); fii:=k; end; procedure tata(v:integer); var i:integer; begin for i:=1 to n do if tavi=i then begin taii:=v; tavi:=0; end end; procedure oras; var max,i,j:integer; begin max:=0; for i:=1 to n do if fii(i)>max then max:=fii(i);
writeln('Orasele optime sunt:'); for i:=1 to n do if fii(i)=max then begin
write(i,' '); tata(i);
write('Vectorul tata este:'); for j:=1 to n do write(taji,' ');
writeln; end; end; begin AmainS clrscr; citire;
writeln('Dati vf de pornire!');readln(v); prim;
writeln('Costul arborelui este:',cost); oras; readkey; end.

Problema 2: Se da un graf neorientat.Sa se creeze un arbore partial de cost minim care sa poata fi memorat apoi sub forma unei liste.
Exemplu:

1 2 1 2

6 7
3 4 3 4

ASe foloseste algoritmul lui Prim iar pentru fiecare nou nod introdus se verifica daca parintele sauAsaiiS are mai un fiu sau cel mult unul in cazul in care este chiar varful.Daca sunt indeplinite aceste conditii se adauga varful la arbore ,daca nu se aplica algoritmul lui prim pentru o noua matrice A1.Matricea A1 se obtine din A punand costul mechiei care era minima in A egala cu 0.Se repeta procesul pana s-au introdus n-1 varfuriS
Rezolvare: program arbore_lista; uses crt; type muchie=record vf1,vf2,cost:integer; end; type vector=arraya1..50i of longint; vector1=arraya1..100i of muchie; matrice=arraya1..50,1..50i of longint; var n,i,j,k,v,cost,y,z,m:integer; s,t,s1,t1:vector; x:vector1; a,a1:matrice; f:text; procedure citire; var i,j,m:integer; begin assign(f,'depozit.txt'); reset(f); readln(f,n);m:=0;
while not eof(f) do begin inc(m); read(f,xami.vf1); read(f,xami.vf2); read(f,xami.cost); readln(f); end; for i:=1 to m do begin aaxaii.vf1,xaii.vf2i:=xaii.cost; aaxaii.vf2,xaii.vf1i:=xaii.cost; end;
writeln('Matricea costurilor este:'); for i:=1 to n do begin for j:=1 to n do
write(aai,ji,' ');
writeln; end; end; function fii(y:integer):integer; var k,j:integer; begin k:=0; for j:=1 to n do if taji=y then inc(k); fii:=k; end; procedure prim(a:matrice); var i,j,min:integer; begin min:=maxint; for i:=1 to n do if (saii<>0) then if (aasaii,ii<min) and (aasaii,ii<>0) then begin min:=aasaii,ii; j:=i; end; if (((saji<>v) and (fii(saji)=0)) or ((saji=v) and (fii(saji)<=1))) then begin taji:=saji; cost:=cost+aaj,sajii; saji:=0; for i:=1 to n do if (saii<>0) then if (aai,saiii=0) or (aai,saiii>aai,ji) then if aai,ji<>0 then saii:=j; inc(m); end else begin a1:=a; a1asaji,ji:=0; prim(a1); end; end; begin AmainS clrscr; citire;
writeln('Dati vf de pornire!');readln(v); m:=0; for i:=1 to n do saii:=v; savi:=0; for i:=1 to n do taii:=0; cost:=0; repeat prim(a); until m=n-1;
write('Vectorul tata este: '); for i:=1 to n do

write(taii,' ');
writeln;
writeln('Costul arborelui este:',cost); readkey; end.

Problema 3:Se da un graf orientat si se cere sa se afle daca exista un arbore partial de cost minim.Dar o arborescenta de cost minim?Daca exista sa se afle care este este varful acesteia.
ADaca exista sau nu o arbore de cost minim se poate spune foarte usor daca verificam conexitatea grafului.Daca graful este tare conex atunci putem spune ca exista un arbore partial de cost minim.Un lant de la x la y va avea costul egal cu costul drumui de la x la y plus costul drumului de la y la x.Pentru a verifica daca exista o arborescenta aplicam unul din cei doi algoritmi.Daca,in cazul lui Prim,exista si un alt nod cu taii=0 cu exceptia varfului atunci aceasta nu este arborescenta iar in algoritmul Kruskal,daca multimea B a muchiilor are mai putin de n-1 muchii, atunci nu exista arborescenta.Se aplica algoritmii de n ori pentru fiecare nod drept varf pentru a vedea daca exista o arborescenta de cost minim.Muchiile vor fi orientate iar matricea costurilor nu va fi simetrica.S

program arborescenta; Aafiseaza arborescenta in cazul in care exista unaS uses crt; type muchie=record vf1,vf2,cost:integer; end; type vector=arraya1..100i of longint; vector1=arraya1..100i of muchie; matrice=arraya1..50,1..50i of longint; var n,i,j,k,v,cost:integer; s,t:vector; x:vector1; a:matrice; f:text; procedure citire; var i,j,m:integer; begin assign(f,'orient.txt'); reset(f); readln(f,n);m:=0;
while not eof(f) do begin inc(m); read(f,xami.vf1); read(f,xami.vf2); read(f,xami.cost); readln(f); end; for i:=1 to m do aaxaii.vf1,xaii.vf2i:=xaii.cost;
writeln('Matricea costurilor este:'); for i:=1 to n do begin for j:=1 to n do
write(aai,ji,' ');
writeln; end; end; procedure prim; var i,j,min:integer; begin for i:=1 to n do saii:=v; savi:=0; for i:=1 to n do taii:=0; cost:=0; for k:=1 to n-1 do begin min:=maxint; for i:=1 to n do if (saii<>0) then if (aasaii,ii<min) and (aasaii,ii<>0) then begin min:=aasaii,ii; j:=i; end; taji:=saji; cost:=cost+aasaji,ji; saji:=0; for i:=1 to n do if (saii<>0) then if (aasaii,ii=0) or (aasaii,ii>aaj,ii) then if aaj,ii<>0 then saii:=j; end; end; begin AmainS clrscr; citire;
writeln('Dati vf de pornire!');readln(v); prim;
writeln('Vectorul tata este:'); for i:=1 to n do
write(taii,' ');
writeln('Costul arborelui este:',cost); readkey; end.

Problema 4:Se da un graf conex.Se cere impartirea acestuia in m arbori partiali de cost minim fiecare cu p varfuri.Sa se afiseze acesti arbori.
ACel mai favorabil ar fi algoritmul lui Prim.Acesta se aplica de m ori iar for din procedura va fi de la 1 la p-1.Nodurile care au fost incluse intr-un arbore precedent vor fi trecute in vectorii S si T cu valoarea -;1 iar matricea va fi zero pe liniile si coloanele respective.S

program m_arbori; uses crt; type vector=arraya1..100i of longint; matrice=arraya1..50,1..50i of longint; var n,i,j,k,v,cost,p,m:integer; s,t:vector; a:matrice; f:text; procedure citire; var i,j:integer; begin assign(f,'prim.txt'); reset(f); readln(f,n); for i:=1 to n do begin for j:=1 to n do read(f,aai,ji); readln(f); end;
writeln('Matricea costurilor este:'); for i:=1 to n do begin for j:=1 to n do
write(aai,ji,' ');
writeln; end; end; procedure prim; var i,j,min,h:integer; begin cost:=0; for h:=1 to p-1 do begin min:=maxint; for i:=1 to n do if (saii>0) then if (aasaii,ii<min) and (aasaii,ii<>0) then begin min:=aasaii,ii; j:=i; end; taji:=saji; cost:=cost+aaj,sajii; saji:=0;
write(j,' '); for i:=1 to n do if (saii>0) then if (aai,saiii=0) or (aai,saiii>aai,ji) then if aai,ji<>0 then saii:=j; taji:=-1; saji:=-1; for i:=1 to n do begin aai,ji:=0; aaj,ii:=0; end; end;
write('Costul arborelui este:',cost); end; begin AmainS clrscr; citire;
writeln('Dati vf de pornire!');readln(v);
write('m=');read(m);
write('p=');read(p); for i:=1 to n do saii:=v; savi:=0; for i:=1 to n do taii:=0; for k:=1 to m-1 do begin for i:=1 to n do begin if taii=0 then begin
write(i,' '); prim; for j:=1 to n do if taji=0 then saji:=i; saii:=-1;writeln; end; savi:=-1; tavi:=-1; end; end; readkey; end.