Algoritmi de determinare a arborilor parțiali de cost minim

INTRODUCERE

1. Definiţii

Se numeşte arbore orice graf conex şi fără cicluri. Arborele parţial al unui graf conex G este un graf parţial al lui G, care este arbore.

Un graf (neorientat) şi fără cicluri se numeşte pădure.

Componentele conexe ale unei păduri vor fi arbori. Un arbore cu n varfuri are n-1 muchii.

2. Problema arborelui partial de cost minim

Fie G = (V, E) un graf neorientat conex, unde V este mulţimea nodurilor şi E este mulţimea muchiilor. Fiecărei muchii u din E îi asociem un cost c(u) > 0.

Problema constă în a determina un graf parţial conex A = ( V, E’ ) astfel încât suma costurilor muchiilor din E’ să fie minimă. Se observă că graful parţial de cost minim este chiar un arbore. Într-adevăr A este conex. Dacă A ar conţine un ciclu, se obţine tot un graf parţial conex, având însă un cost mai mic. Deci, A este un arbore.

O problemă economică ce conduce la problema arborelui parţial de cost minim este cea a conectării oraşelor cu cost minim:

Se dau n oraşe precum şi costul conectării anumitor perechi de oraşe. Se cere să se aleagă acele muchii care asigură existenţa unui drum între oricare două oraşe astfel încât costul total al cuplării să fie minim.

Dupa modelarea matematică necesară, o astfel de problemă se reduce la o problemă clasică de teoria grafurilor, deoarece costul unei muchii (i, j) reprezintă costul conectarii directe a oraşelor i si j, iar arborele parţial de cost minim reprezintă modalitatea optimă de a lega direct perechi de oraşe astfel încât în final orice oraş să fie conectat direct sau indirect cu toate celelalte.

Construirea arborelui parţial de cost minim este permisă de către metoda

Greedy. El poate fi obţinut fie prin algoritmul lui Kruskal, fie prin algoritmul lui Prim.

ALGORITMUL LUI KRUSKAL

Algoritmul lui Kruskal este una dintre metodele cunoscute de rezolvare a problemei determinării arborelui parţial de cost minim. Paşii acestui algoritm sunt următorii:

-se alege întâi muchia de cost minim,

-se adaugă repetat muchia de cost minim nealeasă anterior şi care nu formează cu precedentele un ciclu,

-se vor alege n-1 muchii.

(a) (b)

(c) (d)

(e)

Figura 1- Arborele parţial de cost minim obţinut prin algoritmul lui Kruskal