刻寬

圖論中，圖的刻寬（carving width）是由圖定義的數，描述了圖頂點的層次聚類中，分隔聚類的邊數。

定義與例子

刻寬是根據給定圖頂點的分層聚類（稱作「刻」，carving）定義的。刻可以描述為無根二叉樹，其葉上標有給定圖的頂點。從樹上移除任意一條邊，都會將樹分為兩子樹，並相應地將樹上頂點分為兩簇。這樣形成的頂點簇構成了層狀集合族（Laminar set family）：任意兩頂點簇（不僅是移除同一條邊形成的兩互補簇）或不交，或是包含關係。這樣定義的刻寬是連接兩互補簇的最大邊數。圖的刻寬是任何層次聚類的最小刻寬。

刻寬恰為1的圖是匹配。刻寬為2的圖是徑圖與循環圖的不交並形成的圖。刻寬為3的圖是次立方部分2樹，這意味着其最大度為3，並是系列平行圖的子圖。其他圖的刻寬至少為4。

計算複雜度

刻寬的計算總的來說是NP困難的，但在平面圖中可用多項式時間計算。其近似率與平衡割的近似率相仿，目前的最佳近似率為$O({\sqrt {\log n}})$。它還是固定參數可解的：對定值$k$，測試刻寬是否不大於k，若是，則找到實現此寬度的分層聚類可在線性時間內完成。總的來說，在n個頂點、m條邊的重圖上精確計算刻寬可在$O(2^{n}n^{3}\log n\log \log n\log m)$的時間內完成。

相關參數

刻寬是衡量給定圖「有多像樹」的幾個圖寬度參數之一，還有樹寬、枝寬等。圖的枝寬的定義也使用了分層聚類，但使用的是圖的邊，而非頂點，這些稱作枝分解。 將邊附着到端點之一、並將刻的每片葉擴展為表示其附着的邊的子樹，可以將圖的刻轉換為枝分解。用這種結構可以證明，對任何圖，刻寬都不小於枝寬的一半，並不大於度乘枝寬。由於樹寬與枝寬總是互為常因子，因此可用類似的邊界，將刻寬與樹寬聯繫起來。

割寬由圖中跨越割的邊數決定，其定義使用了圖中頂點的線性排序，以及在此排序中分隔前後子集的分隔系統。不同於刻寬，這分隔系統不包括將頂點與其餘頂點分隔，於是（雖然使用了更受限的割族），割寬可以小於刻寬。然而刻寬總不大於割寬與圖最大度兩者中的較大值。