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 să 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.