刻宽

图论中，图的刻宽（carving width）是由图定义的数，描述了图顶点的层次聚类中，分隔聚类的边数。

定义与例子

刻宽是根据给定图顶点的分层聚类（称作“刻”，carving）定义的。刻可以描述为无根二叉树，其叶上标有给定图的顶点。从树上移除任意一条边，都会将树分为两子树，并相应地将树上顶点分为两簇。这样形成的顶点簇构成了层状集合族（Laminar set family）：任意两顶点簇（不仅是移除同一条边形成的两互补簇）或不交，或是包含关系。这样定义的刻宽是连接两互补簇的最大边数。图的刻宽是任何层次聚类的最小刻宽。Template:R

刻宽恰为1的图是匹配。刻宽为2的图是径图与循环图的不交并形成的图。刻宽为3的图是次立方部分2树，这意味着其最大度为3，并是系列平行图的子图。其他图的刻宽至少为4。Template:R

计算复杂度

刻宽的计算总的来说是NP困难的，但在平面图中可用多项式时间计算。Template:R其近似率与平衡割的近似率相仿，Template:R目前的最佳近似率为$O(\sqrt{\log n})$。Template:R它还是固定参数可解的：对定值$k$，测试刻宽是否不大于k，若是，则找到实现此宽度的分层聚类可在线性时间内完成。Template:R总的来说，在n个顶点、m条边的重图上精确计算刻宽可在$O(2^n{n}^3\log n\log \log n\log m)$的时间内完成。Template:R

相关参数

刻宽是衡量给定图“有多像树”的几个图宽度参数之一，还有树宽、枝宽等。图的枝宽的定义也使用了分层聚类，但使用的是图的边，而非顶点，这些称作枝分解。 将边附着到端点之一、并将刻的每片叶扩展为表示其附着的边的子树，可以将图的刻转换为枝分解。用这种结构可以证明，对任何图，刻宽都不小于枝宽的一半，并不大于度乘枝宽。由于树宽与枝宽总是互为常因子，因此可用类似的边界，将刻宽与树宽联系起来。Template:R

割宽由图中跨越割的边数决定，其定义使用了图中顶点的线性排序，以及在此排序中分隔前后子集的分隔系统。Template:R不同于刻宽，这分隔系统不包括将顶点与其余顶点分隔，于是（虽然使用了更受限的割族），割宽可以小于刻宽。然而刻宽总不大于割宽与图最大度两者中的较大值。Template:R