Arbori de Acoperire de Cost Minim

Definitii generale

Ce este un graf ?

• Numim graf o pereche ordonată de mulţimi, notată G=(X,U), unde X este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U este o mulţime de perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz, graful se numeşte orientat, altfel acesta este neorientat.

• Aşadar un graf poate fi reprezentat sub forma unei figuri geometrice alcătuite din puncte (care corespund vârfurilor) şi din linii drepte sau curbe care unesc aceste puncte (care corespund muchiilor sau arcelor).

graf neorientat graf orientat

Ce este un graf ponderat ?

• Un graf ponderat “weighted graph” este un graf în cadrul căruia fiecarui arc îi este asociată o valoare;

• Valoarea asociată arcului are semnificaţia de “cost” a legăturii între cele 2 noduri sau de “distanţa” între noduri.

Ce este Arborele de acoperire de cost minim ?

Fie G=(N,A) un graf conex în care fiecare arc are ataşat un cost c(u,v).

Un arbore de acoperire a lui G este arborele liber care:

• cuprinde toate nodurile din N;

• este subgraf a lui G.

Ce este un graf conex ?

• Spunem că un graf este conex dacă între oricare două vârfuri ale acestuia există cel puţin un drum.

Arbori partiali de cost minim

• Fie G = <V, M> un graf neorientat conex, unde V este multimea varfurilor si M este multimea muchiilor. Fiecare muchie are un cost nenegativ (sau o lungime nenegativa). Problema este sa gasim o submultime A x M, astfel incat toate varfurile din V sa ramina conectate atunci cand sunt folosite doar muchii din A, iar suma lungimilor muchiilor din A sa fie cat mai mica. Cautam deci o submultime A de cost total minim. Aceasta problema se mai numeste si problema conectarii oraselor cu cost minim, avand numeroase aplicatii.

• Graful partial <V, A> este un arbore (Exercitiul 6.11) 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.

•

Proprietatea 6.2 Fie G = <V, M> un graf neorientat conex in care fiecare muchie are un cost nenegativ. Fie W x V o submultime stricta a varfurilor lui G si fie A x M o multime promitatoare de muchii, astfel incat nici o muchie din A nu atinge W. Fie m muchia de cost minim care atinge W. Atunci, A x {m} este promitatoare.

• Demonstratie: Fie B un arbore partial de cost minim al lui G, astfel incat A x B (adica, muchiile din A sunt continute in arborele B). Un astfel de B trebuie sa existe, deoarece A este promitatoare. Daca m x B, nu mai ramane nimic de demonstrat. Presupunem ca m x B. Adaugandu-l pe m la B, obtinem exact un ciclu (Exercitiul3.2). In acest ciclu, deoarece m atinge W, trebuie sa mai existe cel putin o muchie m' care atinge si ea pe W (altfel, ciclul nu se inchide). Eliminandu-l pe m', ciclul dispare si obtinem un nou arbore partial B' al lui G. Costul lui m este mai mic sau egal cu costul lui m', deci costul total al lui B' este mai mic sau egal cu costul total al lui B. De aceea, B' este si el un arbore partial de cost minim al lui G, care include pe m. Observam ca A x B' deoarece muchia m', care atinge W, nu poate fi in A. Deci, A x {m} este promitatoare.

Algoritmul lui Kruskal si Prim (Principii de functionare si limbaj natural)

Algoritmul lui Prim (principiu)

– Fie G=(N,A) şi o funcţie de cost definită pe arcele sale;

– Fie U o submulţime a lui N;

– Dacă (u,v) este un arc cu costul cel mai scăzut, a.î. u € U şi v € NU atunci există un arbore de acoperire minim care include (u,v).