Et partielt k - træ er en slags graf, enten en undergraf af et k - træ eller en graf med en træbredde , der ikke overstiger k . Mange kombinatoriske NP-hårde problemer på grafer løses i polynomiel tid, hvis vi begrænser os til partielle k - træer med en eller anden afgrænset værdi af k .
For enhver fast konstant k , er partielle k træer lukket under driften af at tage graf mindre , og derfor, ved Robertson-Seymour-sætningen , kan en sådan familie af grafer beskrives af et endeligt sæt af forbudte mindre . Delvise 1-træer er nøjagtigt skove , og deres eneste forbudte mindre er en trekant. For delvise 2-træer er den eneste forbudte mindre den komplette graf med fire hjørner . Men efterhånden som værdien af k stiger yderligere, stiger antallet af forbudte mindreårige. For delvise 3-træer er der fire forbudte minorer - den komplette graf med fem toppunkter, den oktaedriske graf med seks toppunkter, Wagner-grafen med otte toppunkter og den femtakkede prismegraf med ti toppunkter [1] .
Mange algoritmiske problemer, der er NP-komplette for vilkårlige grafer, kan effektivt løses for partielle k - træer ved hjælp af dynamisk programmering , hvis trænedbrydning af disse grafer anvendes [2] [3] [4] .
Hvis en familie af grafer har træbredde afgrænset af k , så er det en underfamilie af partielle k -træer. Familier af grafer med denne egenskab omfatter kaktus , pseudoskove , parallel-sekventielle grafer , ydre planære grafer , Halin grafer og Apollonius grafer [1] . For eksempel er parallel-sekventielle grafer en underfamilie af delvise 2-træer. Mere strengt er en graf et delvist 2-træ, hvis og kun hvis nogen af dens hængsler er parallel-serielle.
De kontrolflowgrafer, der opstår ved oversættelse af strukturerede programmer , har også en begrænset træbredde, hvilket gør det muligt at udføre nogle opgaver, såsom registerallokering , effektivt [5] .