fa szélessége

Kapcsolódó fogalmak: 
fa dekompozíció
Rövid szöveges bemutatás: 
A fa szélessége egy mérőszám mely a feladat megoldásának komplexitására ad felső korlátot. A szélességet meg lehet határozni egy gráfra és a gráf fadekompozíciójára. A fa dekompozíciójának szélessége a legnagyobb méretű részprobléma méretétől egyel kisebb. A gráf szélessége pedig az összes fa dekompozíció közül a legkisebb. Levezethető, hogy egy kényszergráffal rendelkező kényszerkielégítési probléma, melynek kényszergráfja felülről korlátos a fa szélessége által az polinomiális időben megoldható.