Arbore parțial

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.

Determinarea unui arbore parțial se poate face folosind un algoritm de parcurgere a grafului (cum ar fi 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.

„Pădurea parțială” este un concept care îl generalizează pe cel de arbore parțial, în cazul grafurilor neconexe. Astfel o pădure parțială este un graf parțial format din reuniunea arborilor parțiali ai fiecărei componente conexe a grafului. O definiție echivalentă este aceea de graf parțial aciclic cu număr maxim de muchii.

Dacă graful este ponderat (fiecare muchie a sa este asociată cu o valoare numerică numită „cost”), 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 univoc.

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.