treewidth（树宽）是图论与算法中的一个参数，用来衡量一个图在结构上“有多像一棵树”。树宽越小，图越接近树结构，很多原本困难的问题就更容易用树分解（tree decomposition）配合动态规划来高效求解。它也常用于参数化复杂性分析。
/triwdθ/
A tree has treewidth 1.
树的树宽是 1。
Many NP-hard problems become tractable on graphs of bounded treewidth using dynamic programming on a tree decomposition.
在树宽有界的图上，许多 NP-困难问题可以通过在树分解上做动态规划而变得可处理（高效可解）。
该词由 tree（树）+ width（宽度）构成，直译为“树的宽度”。它并不是指图的几何宽度，而是用“宽”来形象表达：当把图用树分解表示时，每个“袋（bag）”里需要容纳多少个顶点（更准确地说与袋大小相关），从而反映图偏离树结构的程度。
Select Language