割寬

圖論中，無向圖的割寬（cutwidth）是能滿足下列性質的最小整數k：圖存在頂點排序，使得將頂點劃分為排序的前後子集所得的割至少跨過k條邊。具體點說，若將頂點編上號$v_{1},v_{2},\dots v_{n}$，則$\forall \ell =1,2,\dots n-1$，使$i\leq \ell ,\ j>\ell$的邊$v_{i}v_{j}$最多有k條。

割寬為2的圖。對所示的從左到右的頂點排序，每條垂線最多跨2條邊。

圖的割寬也叫做其耐折數（folding number）。產生割寬的頂點排序以及計算這種排序與割寬的問題，統稱為最小割線性排列（minimum cut linear arrangement）。

與其它參數的關係

割寬常常與圖的樹寬或徑寬相等，不大於徑寬乘以$O(\Delta )$、樹寬乘以$O(\Delta \log n)$，其中$\Delta$是最大度，$n$是頂點數。若一族圖的最大度有界，且圖不含大小無界的完全二元樹的細分，則族中的圖的割寬都有界。次立方圖（subcubic graph，最大度為3的圖）中，割寬等於徑寬加一。

割寬不小於任何圖的最小二等分數，即將頂點分為（儘可能）等大的兩子集時，橫跨兩側的邊數的最小值。圖的任意線性構圖（layout）在達到最佳割寬後，也能將構圖分為前後部，得到具有相同邊數的等分。割寬不大於最大度乘帶寬（bandwidth），即線性排列中分隔任意邊兩端點的最大步數。相比於帶寬，將邊細分為多條邊的路徑後，割寬不變。它與「拓撲帶寬」有密切聯繫，即從給定圖的邊的細分能得到的最小帶寬。具體來說，對任何樹，其都在拓撲帶寬$b^{*}$與稍大的值$b^{*}+\log _{2}b^{*}+2$的區間內。

刻寬（carving width）的定義與割寬類似，都指圖中跨越切口的邊數。然而，刻寬不像割寬那樣使用頂點的線性排序與割的線性序列，而是從頂點的分層聚類中導出的割，這使其與樹寬、枝寬更密切，而同徑寬、帶寬等不太相似。

割寬可為交叉數提供一個下界，這是來自圖繪製（graph drawing）研究的概念。圖的交叉數是指：使頂點只連接自身為端點的邊，在平面上繪製圖時，相交邊對數的最小值。度有界的圖中，交叉數至少與割寬的平方成正比。對度無界的圖，更精確的下界是：

$$\operatorname {crossings} (G)\geq {\frac {1}{1176}}\operatorname {cutwidth} (G)^{2}-\sum _{v\in V(G)}\left({\frac {\deg(v)}{4}}\right)^{2}.$$

其中，校正項與度的平方和成正比，是為解釋割寬平方與該量成正比，但交叉數為零的平面圖所必須的。在另一種圖繪製——書嵌入（book embedding）中，定點被排列在一條線（「書脊」）上，邊則不交叉地排列在稱作「頁」（page）的半平面上，只在書脊處相交。書嵌入的頁寬（page width）是指在相同定點排序下，頁的最大割寬。

計算複雜度

對n個頂點的樹，可在$O(n\log n)$的時間內找到割寬，並構造出最佳寬度的線性構圖。而對更一般的圖，是NP困難的；即使對度不大於3的平面圖，也是NP難的；即使輸入是樹，此問題的加權版本（最小化線性排列割邊的權）也是NP難的。

割寬是最優線性排列問題之一，可通過赫爾德-卡普算法，運用動態規劃在$O(n2^{n})$時間內求解。還有用量子演算法的更快算法，可在$O(1.817^{n})$時間內解決。此外，這算法還是固定參數可解的：對任意定值$c$，都可在線性時間內測出圖的割寬是否大於$c$，若最大是c，則為其找到一個最優頂點排序。以$n,\ c$表示，運行此算法耗時${\textstyle 2^{O(c^{2})}n}$。另一種參數化算法適於少量頂點具有較高的度（使得割寬變大）的圖。若圖的頂點覆蓋大小有界，此算法可將問題轉化為變量更少、變量值受多項式約束的整數規劃。對樹寬有界的圖，由於「樹寬有界」包含割寬與頂點覆蓋數兩個參數，仍不知道此問題能否有效求解。

稠密圖割寬有多項式時間近似算法，而對可能不稠密的圖，已知最佳近似率為${\textstyle O{\bigl (}(\log n)^{3/2}{\bigr )}}$。這來自Tom Leighton與Satish Rao用遞歸二分法對定點排序，將近似割寬減小到最小二分數的方法，在近似率上損失了$\log _{2}n$的因子。將這種遞歸二分法與Sanjeev Arora、Rao、烏梅什·瓦茲拉尼的最小二分數近似算法結合起來，可得所述近似率。在小集合擴展假設下，不可能實現恆定的近似率。

應用

通道布線問題，要在矩形區域內搭建出連接同編號管口的水平「通道」

使用5通道的解決方案

割寬的早期應用如超大規模集成電路設計中的通道布線問題，當中沿集成電路矩形區域的頂部、底部排列的元件的引腳必須通過導體連接起來。若元件可以從左到右自由排列，而元件引腳必須保持相連，那麼這就可以轉化為圖的線性排列的選擇問題，元件對應頂點，邊對應引腳間的導線。圖的割寬決定了電路布線所需通道數。

蛋白質工程中，假設相關圖的割寬有界，可用於加速搜索編碼了蛋白質序列與二級結構的mRNA序列。

割寬問題的一個加權版本適用於有向無環圖，當中線性排序要與邊方向一致，這已用於計算任務序列的調度，調度方式可以最大限度地減少任務本身與維護通信數據所需的最大內存。在資料庫理論中，割寬問題的NP困難性被用於證明：執行連接時，為避免在磁碟與內存間反覆傳輸相同數據塊，同時在有限的內存中進行計算、安排這傳輸的問題，也是NP困難的。

在圖繪製中，割寬除了計算交叉數下界外，還用於研究一種特殊的3維圖繪製，要求邊表示為最多1個折點的不交折線，頂點位於一條線上，頂點與折點必須有整數坐標。繪製這種圖，圖邊界框的最小體積必須至少與割寬乘頂點數成正比。頂點位於軸平行線上方時，總存在具有此體積的繪製。