Un arbore k parțial este un fel de grafic, fie un subgraf al unui arbore k , fie un grafic cu o lățime a arborelui care nu depășește k . Multe probleme combinatorii NP-hard pe grafice sunt rezolvate în timp polinomial, dacă ne restrângem la k -arbori parțiali cu o valoare mărginită a lui k .
Pentru orice constantă fixă k , arborii parțiali k sunt închiși sub operațiunea de a lua minori de graf și, prin urmare, prin teorema Robertson-Seymour , o astfel de familie de grafuri poate fi descrisă de un set finit de minori interzise . Parțial 1-copaci sunt exact păduri și singurul lor minor interzis este un triunghi. Pentru 2 arbori parțiali, singurul minor interzis este graficul complet cu patru vârfuri . Cu toate acestea, pe măsură ce valoarea lui k crește în continuare, numărul minorilor interziși crește. Pentru 3-arbori parțiali, există patru minori interzise — graficul complet cu cinci vârfuri, graficul octaedric cu șase vârfuri, graficul Wagner cu opt vârfuri și graficul cu prismă în cinci puncte cu zece vârfuri [1] .
Multe probleme algoritmice care sunt NP-complete pentru grafice arbitrare pot fi rezolvate eficient pentru k -arborele parțiale folosind programarea dinamică dacă se utilizează descompunerea arborescentă a acestor grafice [2] [3] [4] .
Dacă o familie de grafice are lățimea arborelui mărginită de k , atunci este o subfamilie de arbori k parțiali. Familiile de grafice cu această proprietate includ cactusi , pseudopăduri , grafice paralel-secvențiale , grafice outerplanare , grafice Halin și grafice Apollonius [1] . De exemplu, graficele paralele-secvențiale sunt o subfamilie de 2 arbori parțiali. Mai strict, un grafic este un arbore 2 parțial dacă și numai dacă oricare dintre balamalele sale este paralel-serială.
Graficele fluxului de control care apar la traducerea programelor structurate au, de asemenea, o lățime limitată a arborelui, ceea ce permite ca unele sarcini, precum alocarea registrului , să fie efectuate eficient [5] .