割宽

割宽为2的图。对所示的从左到右的顶点排序，每条垂线最多跨2条边。

图论中，无向图的割宽（cutwidth）是能满足下列性质的最小整数k：图存在顶点排序，使得将顶点划分为排序的前后子集所得的割至少跨过k条边。具体点说，若将顶点编上号$v_1,v_2,\dots v_n$，则$\mathrm{\forall }\ell =1,2,\dots n-1$，使$i\le \ell ,j>\ell$的边$v_i{v}_j$最多有k条。Template:R

图的割宽也叫做其耐折数（folding number）。Template:R产生割宽的顶点排序以及计算这种排序与割宽的问题，统称为最小割线性排列（minimum cut linear arrangement）。Template:R

与其它参数的关系

割宽常常与图的树宽或径宽相等，不大于径宽乘以$O(\mathrm{\Delta })$、树宽乘以$O(\mathrm{\Delta }\log n)$，其中$\mathrm{\Delta }$是最大度，$n$是顶点数。Template:R若一族图的最大度有界，且图不含大小无界的完全二叉树的细分，则族中的图的割宽都有界。Template:R次立方图（subcubic graph，最大度为3的图）中，割宽等于径宽加一。Template:R

割宽不小于任何图的最小二等分数，即将顶点分为（尽可能）等大的两子集时，横跨两侧的边数的最小值。图的任意线性构图（layout）在达到最佳割宽后，也能将构图分为前后部，得到具有相同边数的等分。割宽不大于最大度乘带宽（bandwidth），即线性排列中分隔任意边两端点的最大步数。Template:R相比于带宽，将边细分为多条边的路径后，割宽不变。它与“拓扑带宽”有密切联系，即从给定图的边的细分能得到的最小带宽。具体来说，对任何树，其都在拓扑带宽$b^{*}$与稍大的值$b^{*}+{\log }_2{b}^{*}+2$的区间内。Template:R

刻宽（carving width）的定义与割宽类似，都指图中跨越切口的边数。然而，刻宽不像割宽那样使用顶点的线性排序与割的线性序列，而是从顶点的分层聚类中导出的割，这使其与树宽、枝宽更密切，而同径宽、带宽等不太相似。Template:R

割宽可为交叉数提供一个下界，这是来自图绘制（graph drawing）研究的概念。图的交叉数是指：使顶点只连接自身为端点的边，在平面上绘制图时，相交边对数的最小值。度有界的图中，交叉数至少与割宽的平方成正比。对度无界的图，更精确的下界是：Template:R$$\mathrm{crossings}(G)\ge \frac{1}{1176}\mathrm{cutwidth}(G{)}^2-\sum _{v\in V(G)}{\left(\frac{\mathrm{deg}(v)}{4}\right)}^2.$$其中，校正项与度的平方和成正比，是为解释割宽平方与该量成正比，但交叉数为零的平面图所必须的。Template:R在另一种图绘制——书嵌入（book embedding）中，定点被排列在一条线（“书脊”）上，边则不交叉地排列在称作“页”（page）的半平面上，只在书脊处相交。书嵌入的页宽（page width）是指在相同定点排序下，页的最大割宽。Template:R

计算复杂度

对n个顶点的树，可在$O(n\log n)$的时间内找到割宽，并构造出最佳宽度的线性构图。Template:R而对更一般的图，是NP困难的；即使对度不大于3的平面图，也是NP难的；即使输入是树，此问题的加权版本（最小化线性排列割边的权）也是NP难的。Template:R

割宽是最优线性排列问题之一，可通过赫尔德-卡普算法，运用动态规划在$O(n{2}^n)$时间内求解。Template:R还有用量子演算法的更快算法，可在$O(1.817^n)$时间内解决。Template:R此外，这算法还是固定参数可解的：对任意定值$c$，都可在线性时间内测出图的割宽是否大于$c$，若最大是c，则为其找到一个最优顶点排序。Template:R以$n,c$表示，运行此算法耗时$2^{O(c^2)}n$。Template:R另一种参数化算法适于少量顶点具有较高的度（使得割宽变大）的图。若图的顶点覆盖大小有界，此算法可将问题转化为变量更少、变量值受多项式约束的整数规划。对树宽有界的图，由于“树宽有界”包含割宽与顶点覆盖数两个参数，仍不知道此问题能否有效求解。Template:R

稠密图割宽有多项式时间近似算法，Template:R而对可能不稠密的图，已知最佳近似率为$O((\log n{)}^{3/2})$。Template:R这来自Tom Leighton与Satish Rao用递归二分法对定点排序，将近似割宽减小到最小二分数的方法，在近似率上损失了${\log }_{2}n$的因子。Template:R将这种递归二分法与Sanjeev Arora、Rao、乌梅什·瓦兹拉尼的最小二分数近似算法Template:R结合起来，可得所述近似率。Template:R在小集合扩展假设下，不可能实现恒定的近似率。Template:R

应用

Template:Multiple image 割宽的早期应用如超大规模集成电路设计中的通道布线问题，当中沿集成电路矩形区域的顶部、底部排列的元件的引脚必须通过导体连接起来。若元件可以从左到右自由排列，而元件引脚必须保持相连，那么这就可以转化为图的线性排列的选择问题，元件对应顶点，边对应引脚间的导线。图的割宽决定了电路布线所需通道数。Template:R

蛋白质工程中，假设相关图的割宽有界，可用于加速搜索编码了蛋白质序列与二级结构的mRNA序列。Template:R

割宽问题的一个加权版本适用于有向无环图，当中线性排序要与边方向一致，这已用于计算任务序列的调度，调度方式可以最大限度地减少任务本身与维护通信数据所需的最大内存。Template:R在数据库理论中，割宽问题的NP困难性被用于证明：执行连接时，为避免在磁盘与内存间反复传输相同数据块，同时在有限的内存中进行计算、安排这传输的问题，也是NP困难的。Template:R

在图绘制中，割宽除了计算交叉数下界外，Template:R还用于研究一种特殊的3维图绘制，要求边表示为最多1个折点的不交折线，顶点位于一条线上，顶点与折点必须有整数坐标。绘制这种图，图边界框的最小体积必须至少与割宽乘顶点数成正比。顶点位于轴平行线上方时，总存在具有此体积的绘制。Template:R