径宽

图论中，图[math]\displaystyle{ G }[/math]的径分解（path decomposition）是[math]\displaystyle{ G }[/math]的“加粗”路径图表示。[math]\displaystyle{ G }[/math]的径宽（pathwidth）是衡量形成[math]\displaystyle{ G }[/math]的路径被加粗的程度。更正式地说，径分解是[math]\displaystyle{ G }[/math]的顶点子集序列，使每条边的端点出现在某一子集中，并使每个顶点都出现在子集连续子序列中，径宽等于这样的分解中最大集的大小减一。 径宽也叫做区间厚度（interval thickness，等于[math]\displaystyle{ G }[/math]的区间父图中的最大团大小减一）、顶点分隔数（vertex separation number）或结点搜索数（node searching number）。

径宽与径分解同树宽、树分解关系密切，在图子式理论中起关键作用：在图子式下封闭、不含所有森林的图族可描述为径宽有界，子式闭图族的一般结构理论中出现的“涡”（vortex）的径宽也有界。径宽与径宽有界图在超大规模集成电路设计、图绘制、计算语言学等领域也有应用。

计算任意图的径宽、甚至精确近似径宽都是NP困难的。不过，这问题是固定参数可解的：测试图的径宽是否为[math]\displaystyle{ k }[/math]，耗时与图的大小呈线性关系，而与[math]\displaystyle{ k }[/math]呈上指数关系。另外，对树之类的特殊图，径宽可在多项式时间内算得，而不依赖于[math]\displaystyle{ k }[/math]。对图的径分解使用动态规划，可以将图算法中很多问题在径宽有界图上高效解决。径分解也可测量树宽有界图上动态规划算法的空间复杂度。