Osittainen k - puu on eräänlainen graafi, joko k - puun osagraafi tai graafi, jonka puunleveys ei ole suurempi kuin k . Monet graafien kombinatoriset NP-kovat tehtävät ratkeavat polynomiajassa, jos rajoitumme osittaisiin k -puihin, joilla on jokin rajoitettu arvo k .
Minkä tahansa kiinteän vakion k kohdalla osittaiset k -puut suljetaan graafisen alareunojen ottamisen yhteydessä, ja siksi Robertson-Seymour-lauseen mukaan tällainen graafiperhe voidaan kuvata rajallisella kiellettyjen mollien joukolla . Osittaiset 1-puut ovat täsmälleen metsiä ja niiden ainoa kielletty sivu on kolmio. Osittaisissa 2-puissa ainoa kielletty sivu on täydellinen neljän kärjen graafi . Kuitenkin, kun k :n arvo kasvaa edelleen, kiellettyjen alaikäisten määrä kasvaa. Osittaisilla 3-puilla on neljä kiellettyä ala-arvoa: täydellinen graafi, jossa on viisi kärkeä, oktaedrigraafi , jossa on kuusi pistettä, Wagnerin graafi , jossa on kahdeksan pistettä, ja viisipisteinen prismagraafi, jossa on kymmenen kärkeä [1] .
Monet algoritmiset ongelmat, jotka ovat NP-täydellisiä mielivaltaisille kaavioille, voidaan ratkaista tehokkaasti osittaisille k - puille dynaamisen ohjelmoinnin avulla, jos käytetään näiden graafien puuhajottelua [2] [3] [4] .
Jos graafiperheen puunleveys on k rajattu , se on osittaisten k -puiden alaperhe . Tämän ominaisuuden omaavia graafiperheitä ovat kaktukset , pseudometsät , rinnakkaiset peräkkäiset graafit , ulkotason graafit , Halinin graafit ja Apolloniuksen graafit [1] . Esimerkiksi rinnakkaiset peräkkäiset graafit ovat osittaisten 2-puiden alaperhe. Tarkemmin sanottuna graafi on osittainen 2-puu, jos ja vain jos jokin sen saranoista on rinnakkaissarja.
Strukturoituja ohjelmia käännettäessä esiintyvillä ohjausvuokaavioilla on myös rajoitettu puun leveys, mikä mahdollistaa joidenkin tehtävien, kuten rekisterin allokoinnin , suorittamisen tehokkaasti [5] .