Arborele parțial de cost minim

În multe cazuri informațiile utile dintr-un întreg graf pot fi concentrate într-un arbore de acoperire al său.

Pentru un graf conex, arborele parțial de cost minim (APM) este un subgraf cu număr minim de muchii dar care permite în continuare interconectarea între toate nodurile. În plus, suma costurilor muchiilor este minimă.

Se disting doi algoritmi (ambii Greedy) care oferă APM-ul unui graf: Kruskal (bazat pe selecție de muchii) și Prim (bazat pe selecție de noduri).