/ 
/ 
Arbore parţial
De la Wikipedia, enciclopedia liberă
|
|
Dat fiind un graf neorientat conex, se numeste arbore parţial al grafului un graf parţial cu proprietatea că este arbore. Intuitiv, un arbore parţial este un arbore obţinut prin eliminarea unor muchii din graf.
Un arbore parţial al unui graf neorientat conex poate fi definit ca un graf parţial conex cu număr minim de muchii, sau un graf parţial aciclic cu număr maxim de muchii.
[modifică] Determinarea unui arbore parţial
Determinarea unui arbore parţial se poate face folosind un algoritm de parcurgere a grafului(Breadth First Search sau Depth First Search). În acest caz se obţine un arbore parţial cu rădăcină, care poate fi reprezentat prin intermediul vectorului de taţi.
[modifică] Pădure parţială
Padurea parţială este un concept care îl generealizează pe cel de arbore parţial, în cazul grafurilor neconexe. Astfel o pădure parţială reprezintă un graf parţial format din reuniunea arborilor parţiali a fiecărei componente conexe a grafului. O definiţie echivalentă ar fi aceea de graf parţial aciclic cu număr maxim de muchii.
[modifică] Arbore parţial de cost minim
Dacă graful este ponderat, se pune problema determinării unui arbore parţial pentru care suma costurilor muchiilor să fie minimă.
Pentru un graf conex, pot exista mai mulţi arbori parţiali de cost minim, dar costul arborelui parţial de cost minim este unic.
Pentru a determina arborele parţial de cost minim asociat unui graf se poate folosi Algoritmul lui Prim, dacă graful este memorat sub formă de matrice de adiacenţă, sau Algoritmul lui Kruskal, dacă graful este memorat prin lista de muchii.
