...bore 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 X1 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 I1,2S, I2,3S, I4,5S, I6,7S, I1,4S, I2,5S, I4,7S, I3,5S, I2,4S, I3,6S, I5,7S, I5,6S si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 1. INCLUDEPICTURE httpvega.unitbv.roandonieCarteasEBimagescap6cap6s1
3.gif t MERGEFORMATINET Figura 1 Un graf si arborele sau partial de cost minim.PasulMuchia considerataComponentele conexe alesubgrafului X, AInitializareI1S, I2S, I3S, I4S, I5S, I6S, I7S1I1, 2SI1, 2S, I3S, I4S, I5S, I6S, I7S2I2, 3SI1, 2, 3S, I4S, I5S, I6S, I7S3I4, 5SI1, 2, 3S, I4, 5S, I6S, I7S4I6, 7SI1, 2, 3S, I4, 5S, I6, 7S5I1, 4SI1, 2, 3, 4, 5S, I6, 7S6I2, 5Srespinsa formeaza ciclu7I4, 7SI1, 2, 3, 4, 5, 6, 7STabelul 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 I1,2S, I2,3S, I4,5S, I6,7S, I1,4S, I4,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 Ise face sortarea intr-un vector v a muchiilor in ordine var i,k,mininteger crescatoare a costurilor muchiilorS cvectorbegin cak0 repeat minmaxint for i1 to m do if ciis.costmin and ciis.cost0 then begin minciis.cost ji end inck viksj cijs.cost0 until kmendprocedure kruskalvar i,k,jintegerbegin k0 for i1 to m do begin if xiaiviiss.vf1s0 and xiaiviiss.vf2s0 then Iambele extremitati begin formeaza un arbore cu un singur nodS bbiviiss inck xiaiviiss.vf1sk xiaiviiss.vf2sk end else if xiaiviiss.vf1sxiaiviiss.vf2s then Ise verifica daca extremitatile begin muchiei sunt din arbori diferitiS bbiviiss if xiaiviiss.vf1s0 and xiaiviiss.vf2s0 then begin for j1 to n do if xijsxiaiviiss.vf1s and aiviiss.vf1j then xijsxiaiviiss.vf2s xiaiviiss.vf1sxiaiviiss.vf2s end if xiaiviiss.vf1s0 then xiaiviiss.vf1sxiaiviiss.vf2s if xiaiviiss.vf2s0 then xiaiviiss.vf2sxiaiviiss.vf1s end sumasumaaiviiss.cost endendbegin ImainSclrscr citire for i1 to m do viis0 sortare ritelnVectorul sortat in ordinea muchiilor este for i1 to m do riteviis, riteln for i1 to n do xiis0 bis kruskal ritelnMuchiile arborelui sunt suma0 for i1 to m do if i in b then begin ritelnMuchia ,i,,aiis.vf1, ,aiis.vf2, de cost ,aiis.cost sumasumaaiis.cost end riteCostul arborelui este,sumareadkeyend.2Algoritmul 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 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 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. PasulMuchia considerataInitializareI1S1I2, 1SI1, 2S2I3, 2SI1, 2, 3S3I4, 1SI1, 2, 3, 4S4I5, 4SI1, 2, 3, 4, 5S5I7, 4SI1, 2, 3, 4, 5, 6S6I6, 7SI1, 2, 3, 4, 5, 6, 7STabelul 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, XI1,2,...,nS matricea simetrica C da costul fiecarei muchii, cu Cii,jsmaxint, daca muchia Ii,jS nu exista. Folosim doi vectori,vectorul parintilor Tiis si un vector siis. Vectorul T este vectorul tata in care ,pentru fiecare nod i din X,Tiis este egal cu parintele lui i.Vectorul S este definit astfel Siis 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 ii,ks cu k neapartinand arborelui partial Initial vectorul tata este 0 peste tot iar vectorul S este definit astfelSivs0 si Siisv pentru iv,unde v este varful arborelui.Se alege apoi muchia de cost minim i,j care are numai o extremitate in arborele partial construit adica Siis0 iar Sijs0.Se ...
Download