ARBORELE PARTIAL DE COST MINIM

ARBORELE PARTIAL DE COST MINIM

Definitie. Fie G=(V,M) un graf. Se numeste arbore partial, al lui G, un graf partial al sau, care , in plus, este si arboreal.

Exemplu: Daca din graful:

se elimina muchiile [2,4] si [1,3], se obtine un graf partial, care este si arbore(conex si fara cicluri), deci se obtine un arbore partial.

Propozitie. Fie G=(V,M) un graf. Graful G contine un arbore partial daca si numai daca este conex.

Definitie. Fie G=(V,M) un graf conex si H=(V,M₁) un arbore partial al sau. Definim costul arborelui partial H ca fiind suma costurilor muchiilor sale.

Exempul: Fie graful din figura de mai jos (costul fiecarei muchii fiind scris pe ea).

Considerand arborele partial al sau, H, care se obtine eliminand muchiile [2,4] [3,4] putem calcula costul sau, conform definitiei de mai sus, astfel: cost(H)=cost([l,2])+cost([l,4])+cost([2,3])=l 1+13+15=39