Částečný k - strom je druh grafu, buď podgraf k - stromu nebo graf se šířkou stromu nepřesahující k . Mnoho kombinatorických NP-těžkých problémů na grafech je vyřešeno v polynomiálním čase, pokud se omezíme na parciální k -stromy s nějakou omezenou hodnotou k .
Pro nějakou pevnou konstantu k , částečné k stromy jsou uzavřeny pod operací braní graph minors , a proto, Robertson-Seymour teorém , taková rodina grafů může být popsána konečnou množinou zakázaných minors . Částečné 1-stromy jsou přesně lesy a jejich jedinou zakázanou minoritou je trojúhelník. Pro částečné 2-stromy je jedinou zakázanou vedlejší činností úplný čtyřvrcholový graf . S dalším zvyšováním hodnoty k však roste počet zakázaných nezletilých. Pro částečné 3-stromy existují čtyři zakázané minory — úplný graf s pěti vrcholy, oktaedrický graf se šesti vrcholy, Wagnerův graf s osmi vrcholy a pěticípý hranolový graf s deseti vrcholy [1] .
Mnoho algoritmických problémů, které jsou NP-úplné pro libovolné grafy, lze pro parciální k -stromy efektivně vyřešit pomocí dynamického programování , pokud se použije stromová dekompozice těchto grafů [2] [3] [4] .
Pokud má rodina grafů šířku stromu ohraničenou k , pak je to podrodina částečných k -stromů. Rodiny grafů s touto vlastností zahrnují kaktusy , pseudolesy , paralelní sekvenční grafy , vnější rovinné grafy, Halinovy grafy a Apolloniovy grafy [1] . Například paralelně-sekvenční grafy jsou podrodinou částečných 2-stromů. Přesněji řečeno, graf je částečný 2-strom právě tehdy, když je některý z jeho pantů paralelně sériový.
Grafy řídicích toků , které se vyskytují při překladu strukturovaných programů , mají také omezenou šířku stromu, což umožňuje některé úkoly, jako je alokace registrů , provádět efektivně [5] .