木分解
これは、「 X i {\displaystyle X_{i}} , X j {\displaystyle X_{j}} , X k {\displaystyle X_{k}} がノードで、 X k {\displaystyle X_{k}} が X i {\displaystyle X_{i}} から X j {\displaystyle X_{j}} へのパス上にあるならば、 X i ∩ X j ⊆ X k {\displaystyle X_{i}\cap X_{j}\subseteq X_{k}} である」という条件と同値である。
木分解は一意には定まらない。例えば、自明な木分解として、全ての頂点を含む単一のノードからなる木分解を考えることができる。
台となる木が道グラフであるような木分解を道分解と呼ぶ。このような特殊なタイプの木分解から得られる幅のパラメータは道幅として知られている。
木幅kの木分解(X, T = (I, F))は、 ∀ i ∈ I : | X i | = k + 1 {\displaystyle \forall i\in I:|X_{i}|=k+1} と ∀ ( i , j ) ∈ F : | X i ∩ X j | = k {\displaystyle \forall (i,j)\in F:|X_{i}\cap X_{j}|=k} を満たすときsmoothであるという。