Ett partiellt k - träd är ett slags graf, antingen en subgraf till ett k - träd eller en graf med en trädbredd som inte överstiger k . Många kombinatoriska NP-hårda problem på grafer löses i polynomtid, om vi begränsar oss till partiella k -träd med något avgränsat värde på k .
För varje fast konstant k , är partiella k träd stängda under driften av att ta grafen minors , och därför, genom Robertson-Seymours sats , kan en sådan familj av grafer beskrivas av en ändlig uppsättning av förbjudna minors . Partiella 1-träd är exakt skogar och deras enda förbjudna mindre är en triangel. För partiella 2-träd är den enda förbjudna mindre den fullständiga grafen med fyra vertex . Men när värdet på k ökar ytterligare, ökar antalet förbjudna minderåriga. För partiella 3-träd finns det fyra förbjudna minorer - den kompletta grafen med fem hörn, den oktaedriska grafen med sex hörn, Wagnergrafen med åtta hörn och den femuddiga prismagrafen med tio hörn [1] .
Många algoritmiska problem som är NP-kompletta för godtyckliga grafer kan effektivt lösas för partiella k -träd med dynamisk programmering om träduppdelning av dessa grafer används [2] [3] [4] .
Om en familj av grafer har en trädbredd som begränsas av k , så är det en underfamilj av partiella k -träd. Familjer av grafer med denna egenskap inkluderar kaktusar , pseudoskogar , parallellsekventiella grafer , ytterplanargrafer , Halingrafer och Apolloniusgrafer [1] . Till exempel är parallellsekventiella grafer en underfamilj av partiella 2-träd. Mer strikt är en graf ett partiellt 2-träd om och endast om något av dess gångjärn är parallellt-seriellt.
Styrflödesgraferna som uppstår vid översättning av strukturerade program har också en begränsad trädbredd, vilket gör att vissa uppgifter, såsom registerallokering , kan utföras effektivt [5] .