ARBORI PARŢIALI DE COST MINIM

 

        Definiţie:  Se numeşte arbore un graf conex şi care nu conţine cicluri.

        Fiecărei muchii (i,j) din acest graf îi este asociat un număr ce reprezintă costul muchiei (i,j).

        Fie G=(X,U) un graf neorientat şi conex. Prin eliminarea unor muchii din G se obţine un graf parţial al lui G. Dacă acesta este arbore se va numi arbore parţial. Definim costul unui arbore parţial ca suma costurilor muchiilor sale. Problema principală este obţinerea unui arbore parţial de cost minim adică:

        - între oricare două noduri din arbore sa existe drum;

        - suma muchiilor să fie minimă.

 

     

Unul dintre algoritmii de determinare al arborelui de cost minim este algoritmul lui Kruskal.

 

Prezentarea algoritmului

 

Pasul 1.     Dintre toate muchiile grafului se alege muchia de valoare minimă (maximă). Dacă minimul este multiplu se alege la întâmplare una din muchiile respective. Deoarece acest "la întâmplare" trebuie cumva tradus în limbajul calculatorului, în cazul implementării unui program bazat pe acest algoritm, vom perturba din start valorile muchiilor, la k muchii cu aceiaşi valoare V adunând respectiv valorile e, 2e, ... , ke, unde e este foarte mic (în orice caz, ke mai mic decât diferenţa dintre valoarea acestor arce si valoarea imediat superioară a unui arc), pozitiv.

Pasul 2.    Dintre toate muchiile rămase, se alege cea de valoare minimă (maximă);

Pasul 3.    Dintre toate muchiile rămase, se alege cea de valoare minimă (maximă), astfel încât să nu se formeze cicluri cu cele deja alese;

Pasul 4.    Se reia algoritmul de la pasul 3 până se colectează n-1 muchii.

 

 

        Vom demonstra in continuare că acest algoritm este corect. În primul rând faptul că muchiile se sortează în ordine crescătoare, după cost, ne asigură faptul că muchiile ce vor forma arborele vor fi cele ce au costul cel mai mic dintre toate. De asemenea numărul de muchii trebuie să fie n-1 pentru că dacă ae fi mai mic atunci sigur există vârfuri izolate, iar dacă este mai mare atunci înseamnă câ există cel puţin o legatură în plus şi deci există ciclu în arborele respectiv

 

 

       De exemplu, pentru graful de mai jos :

 

 

       

         arborele de cost minim este :

 

          şi s-a obţinut prin eliminarea muchiilor (1,3) şi (2,4).

 

        Dacă o muchie are un cost mai mic decât altă muchie din graf nu este obligatoriu ca acea muchie facă parte din arbore. În exemplul de mai sus muchia (1,5) are costul 7, mai mare decât costul muchiilor (1,3) şi (2,4) şi totuşi ea face parte din arbore, iar cele două nu. Scopul algoritmului este acela de a gasi muchiile ce au împreună costul cel mai mic şi între oricare două noduri să existe drum.