Arbori partiali de cost minim
Un arbore este un graf conex si fara cicluri.
Fiind dat un graf conex ponderat G (X, G, c) care descrie posibilitatile de conectare (construirea unor legaturi directe) intre diferite perechi de virfuri din X si costurile acestora, sa se determine un numar minim de legaturi care trebuie construite astfel incit oricare doua virfuri sa fie conectate (direct sau indirect) si costul total sa fie minim. Sintem condusi la urmatoarea
Problema.
Fie un graf neorientat ponderat G = (X, G, c). Sa se determine un arbore T = (X, V) de cost minim
(figura 1): dintre toti arborii care se pot obtine din graful G, T
are costul minim, adica 
este minima.
Figura 1. Un graf neorientat ponderat; arbore
partial de cost minim marcat cu linii continue.
Aplicatie Intr-o tara subdezvoltata trebuie reparata infrastructura rutiera. Se cunoaste pentru fiecare artera costul reparatiei. Ce drumuri trebuie reparate mai intii?
1. Algoritmul lui Prim
Acest algoritm foloseste o strategie Greedy pentru a conduce la rezultatul final, ca si algoritmul Dijkstra cu care se aseamana foarte mult.
Algoritm Prim - varianta descriptiva;
Intrare. Un graf neorientat ponderat (X, G, c).
Iesire. Un arbore partial T (X, V ) de cost minim.
begin
S (multimea S se initializeaza cu un virf oarecare s al
multimii X)
V (multimea de arce)
repeat (n-1 iteratii) begin
(x,y) o muchie de cost minim care are un virf x in S
si celalalt virf y in X S;
S S 
V V
end
end (algoritm).
Se pleaca initial cu o lista vida de muchii; ca si virf de plecare pentru multimea S putem lua orice virf s din X. La fiecare pas se alege o muchie care uneste un virf din multimea S cu un altul din afara acesteia si care are costul minim; acest virf se adauga la multimea S.
Prezentam mai jos o descriere a algoritmului lui Prim care poate fi usor implementata.
Algoritm Prim - varianta pentru implementare (Burdescu, p 99-104);
Intrare. Un graf conex ponderat (X, G, c).
Iesire. Un arbore partial T = (X, V ) de cost minim.
begin
S X; V
for (each x I X) do begin
p[x] p[x] x;
end
p[s] (s este un virf oarecare din X)
Actualizeaza reprezentarea cuplului (S, p
while (S ) do begin
x Min(S, p (extrage un virf x I S cu marca p minima)
if (p[x] x) then
V V
for
(each y I G (x)
S) do begin
if p[y] > c(x,y)) then begin
p[y] c(x,y); p[y x;
Actualizeaza reprezentarea cuplului (S, p
end
end
end
end (algoritm).
2. Algoritmul lui Kruskal
Prezentam in continuare o paralela intre algoritmul lui Prim prezentat mai sus si algoritmul lui Kruskal:
- ambii algoritmi folosesc o strategie de tip Greedy pentru a determina un arbore de cost minim;
- algoritmul lui Prim construieste arborele pornind de la un virf oarecare si adauga muchii avind costul minim la un singur arbore care se extinde;
- algoritmul lui Kruskal adauga muchii care pot forma la un moment dat mai multi subarbori distincti, care pe parcurs se conecteaza si in final formeaza unul singur;
- algoritmul lui Prim foloseste o reprezentare a grafului bazata pe functia G
- algoritmul lui Kruskal foloseste o reprezentare a grafului bazata pe lista arcelor.
Algoritm Kruskal - varianta descriptiva;
Intrare. Un graf ponderat (X, U, c).
Iesire. Un arbore partial de cost minim T (X, V ).
begin
V
repeat (n 1 iteratii) begin
u (x,y) muchia de cost minim care nu a fost aleasa din U,
si nu formeaza un ciclu cu muchiile din V;
V V 
end;
end (algoritm).
Inainte de a prezenta o descriere a algoritmului lui Kruskal care poate fi usor implementata, sa facem citeva observatii.
Sa reamintim faptul ca operatia de baza in algoritmul lui Kruskal este cautarea unei muchii de cost minim care uneste doua componente conexe distincte determinate pina in acel moment. Am divizat aceasta operatie in trei parti: cauta o muchie de cost minim, determina daca o muchie data uneste doua componente conexe distincte, si adauga o muchie noua la graful construit pina in acel moment - astfel se obtine din doua componente conexe una singura.
Pentru a rezolva corect prima problema trebuie ca, in cazul in care o muchie nu poate fi adaugata la graful care se construieste (deoarece ambele capete apartin aceleiasi componente conexe), aceasta sa nu mai fie folosita deloc, deoarece componenta conexa nu va fi sparta in viitor. Astfel este suficient sa consideram muchiile grafului G ordonate crescator dupa cost.
Cea mai simpla solutie este ordonarea tuturor muchiilor dupa cost, care necesita un timp de ordin O(m log n).
Urmatoarele doua operatii se rezolva folosind o structura de date auxiliara (U-arbori: Larry, Denenberg, p 445-446) (Burdescu, p 92-98), detaliata in sectiunea urmatoare:
- determina, pentru fiecare virf, din ce componenta face parte;
- efectueaza reuniunea a doua componente.
In algoritmul descris mai jos, Init(M, X ) initializeaza o lista M a componentelor conexe. Fiecare componenta are un virf special numit reprezentantul multimii.
Functia Identif(y,M) determina reprezentantul componentei conexe care il contine pe y.
Procedura Union(s,t,M) determina reuniunea a doua componente conexe care le contin pe s, respectiv pe t.
Algoritm Kruskal - varianta pentru implementare;
Intrare. Un graf ponderat (X, U, c).
Iesire. Un arbore partial de cost minim T (X, V ).
begin
Q masiv cu muchiile grafului ordonate crescator dupa cost;
V Init(M, X );
l k
while (l < n) and k < m do begin
(x, y) muchia de pe pozitia k din Q;
s Identif(x, M); t Identif(y, M);
k k
if (s t) then begin
Union(s, t,
M); V V ;
l l
end
end
end (algoritm).
In final, daca graful initial este conex, se obtine (l n). Aceasta afirmatie va fi justificata in sectiunea urmatoare.
3. U-arbori
Fie o multime X care are n elemente. Prima operatie pe care o efectuam este formarea unei partitii din n submultimi, fiecare avind exact un element. Aceasta este operatia de initializare.
In continuare presupunem ca avem o partitie M a multimii X care are k submultimi (k n). Consideram de asemenea ca fiecare submultime are un virf special numit reprezentantul multimii. In aceste conditii definim inca doua operatii pe care le efectuam pe aceasta partitie.
Fiind dat un element x, care este submultimea care il contine? Concret, care este reprezentantul submultimii respective?
Se dau doua elemente s si t, fiecare fiind reprezentantul unei submultimi. Sa se determine reuniunea celor doua submultimi. Evident, in aceasta situatie unul din cele doua elemente va deveni reprezentantul noii submultimi astfel formate.
Partitia M este reprezentata printr-un masiv de n elemente, fiecare element de pe pozitia x (x I X) avind doua cimpuri, r si h, care ne dau informatii despre statutul elementului x. Cimpul r indica daca x este reprezentantul submultimii din care face parte (r x), sau informatia despre reprezentantul acesteia trebuie cautata in alta parte: concret, la elementul indicat de r. Componenta h are semnificatie numai pentru acel element x care este reprezentantul submultimii, si indica distanta maxima de la acesta la oricare din elementele submultimii.
Figura 2 ne sugereaza de ce aceasta structura se numeste U-arbore (in engleza Up-tree: Larry, Denenberg, p 308-316). Un element al structurii indica in sus spre un altul care face parte din aceeasi submultime, si conduce la reprezentantul submultimii.
Figura 2. O padure de U-arbori.
Elementele partitiei M au urmatoarele valori:
De exemplu, virful x3 a fost la un moment dat reprezentantul unei submultimi si a avut asociata inaltimea 2. Acum el indica spre x4, actualul reprezentant, care are asociata inaltimea 3.
Procedura Init(partitie M; multime X);
begin
for (each x I X) do begin
M[x].r x; (creeaza o multime formata numai din virful x)
M[x].h 1; (fiecare multime formata are inaltimea 1)
end
end (procedura);
Functia Identif(x, M) determina reprezentantul componentei conexe care il contine pe x.
Functia Identif(virf x, partitie M);
begin
if (M[x].r x) then return x;
else return Identif(M[x].r);
end (functie);
Procedura Union(s, t, M) determina reuniunea a doua componente conexe care au ca si reprezentanti pe s, respectiv pe t.
Procedura Union(virfuri s, t; partitie M);
begin
if (M[s].h < M[t].h) then (multimea lui s are inaltimea mai mica)
M[s].r t; (s va apartine de acum multimii lui t)
(multimea lui t isi pastreaza inaltimea)
else
if (M[s].h > M[t].h) then (multimea lui t are inaltimea mai mica)
M[t].r s; (t va apartine de acum multimii lui s)
(multimea lui s isi pastreaza inaltimea)
else begin(cele doua multimi au aceeasi inaltime)
M[s].r t; (nu are importanta cum le asociem)
M[t].h M[t].h 1; (daca l-am asociat pe s lui t)
end (inaltimea lui t creste cu 1)
end (procedura);
Initializarea partitiei M se efectueaza intr-un timp de ordin O(n). Reuniunea a doua submultimi se efectueaza intr-un timp de ordin O
Pentru a analiza complexitatea functiei Identif sa facem urmatoarele observatii. Daca avem doua elemente, dupa reuniune se obtine o structura cu inaltimea 2. O structura cu inaltimea 3 se obtine, in cel mai defavorabil caz, din reuniunea a doua structuri avind fiecare inaltimea 2. Cel mai defavorabil caz este dat de o componenta conexa care are un numar minim de elemente si conduce la o inaltime maxima. In cazul general, daca multimea initiala are 2l elemente, se poate ajunge in final la o structura avind inaltimea l 1. Deducem ca functia Identif se executa intr-un timp de ordin O(log n).
Teorema 1. Fiind dat un graf neorientat ponderat, un arbore partial de cost minim poate fi determinat intr-un timp de ordin O(m log n).
Ambii algoritmi se opresc dupa ce au fost selectate n-1 arce. Sa aratam ca in final se obtine intr-adevar un arbore, studiind algoritmul lui Prim. Dupa primul pas avem intr-adevar un arbore partial cu doua virfuri unite printr-o muchie. Sa presupunem ca dupa k-1 pasi avem un subarbore partial cu k virfuri din S si k-1 muchii din V. La urmatorul pas unul din virfurile multimii S se uneste printr-o muchie cu un virf din multimea X S si obtinem un arbore partial cu k 1 virfuri si k muchii. Nu se obtine nici un ciclu: pentru aceasta ar fi trebuit ca virful y ales sa fi fost deja conectat cu unul din virfurile din S, ori virful y nu a fost ales pina acum. Rezulta
Teorema 2. Un arbore T (X, V ) are |X |-1 muchii.
