查看“︁割宽”︁的源代码

[[File:Cutwidth 2 graph.svg|thumb|upright=1.35|割宽为2的图。对所示的从左到右的顶点排序，每条垂线最多跨2条边。]]
[[图论]]中，[[无向图]]的'''割宽'''（cutwidth）是能满足下列性质的最小整数''k''：图存在[[顶点 (图论)|顶点]]排序，使得将顶点划分为排序的前后子集所得的[[割]]至少跨过''k''条边。具体点说，若将顶点编上号<math>v_1,v_2,\dots v_n</math>，则<math>\forall\ell=1,2,\dots n-1</math>，使<math>i\le\ell,\ j>\ell</math>的边<math>v_iv_j</math>最多有''k''条。{{r|chung}}

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

==与其它参数的关系==
割宽常常与图的[[树宽]]或[[径宽]]相等，不大于径宽乘以<math>O(\Delta)</math>、树宽乘以<math>O(\Delta\log n)</math>，其中<math>\Delta</math>是最大度，<math>n</math>是顶点数。{{r|korsol|chusey}}若一族图的最大度有界，且图不含大小无界的[[完全二叉树]]的细分，则族中的图的割宽都有界。{{r|chusey}}次立方图（subcubic graph，最大度为3的图）中，割宽等于径宽加一。{{r|maksud}}

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

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

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

==计算复杂度==
对''n''个顶点的[[树 (图论)|树]]，可在<math>O(n\log n)</math>的时间内找到割宽，并构造出最佳宽度的线性构图。{{r|yannakakis}}而对更一般的图，是[[NP困难]]的；即使对度不大于3的[[平面图 (图论)|平面图]]，也是NP难的；即使输入是树，此问题的加权版本（最小化线性排列割边的权）也是NP难的。{{r|monsud}}

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

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

==应用==
{{multiple image|width=300|direction=vertical
|image1=ChannelRouteProblem.png|caption1=通道布线问题，要在矩形区域内搭建出连接同编号管口的水平“通道”
|image2=ChannelRouteSolution.svg|caption2=使用5通道的解决方案}}
割宽的早期应用如[[超大规模集成电路]]设计中的[[通道布线]]问题，当中沿[[集成电路]]矩形区域的顶部、底部排列的元件的引脚必须通过导体连接起来。若元件可以从左到右自由排列，而元件引脚必须保持相连，那么这就可以转化为图的线性排列的选择问题，元件对应顶点，边对应引脚间的导线。图的割宽决定了电路布线所需通道数。{{r|maksud}}

[[蛋白质工程]]中，假设相关图的割宽有界，可用于加速搜索编码了蛋白质序列与[[核酸二级结构|二级结构]]的[[mRNA]]序列。{{r|bfhv}}

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

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

== 参考文献 ==
{{reflist|refs=

<ref name=abikpv>{{cite conference
 | last1 = Ambainis | first1 = Andris
 | last2 = Balodis | first2 = Kaspars
 | last3 = Iraids | first3 = Jānis
 | last4 = Kokainis | first4 = Martins
 | last5 = Prūsis | first5 = Krišjānis
 | last6 = Vihrovs | first6 = Jevgēnijs
 | editor-last = Chan | editor-first = Timothy M.
 | doi = 10.1137/1.9781611975482.107
 | mr = 3909576
 | pages = 1783–1793
 | publisher = Society for Industrial and Applied Mathematics
 | title = Proceedings of the Thirtieth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019
 | year = 2019| arxiv = 1807.05209
 }}</ref>

<ref name=afk>{{cite journal
 | last1 = Arora
 | first1 = Sanjeev
 | last2 = Frieze
 | first2 = Alan
 | last3 = Kaplan
 | first3 = Haim
 | doi = 10.1007/s101070100271
 | issue = 1, Ser. A
 | journal = Mathematical Programming
 | mr = 1892295
 | pages = 1–36
 | title = A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
 | url = http://www.cs.princeton.edu/~arora/pubs/assign.ps
 | volume = 92
 | year = 2002
 | access-date = 2024-01-29
 | archive-date = 2023-04-09
 | archive-url = https://web.archive.org/web/20230409092429/https://www.cs.princeton.edu/~arora/pubs/assign.ps
 | dead-url = no
 }}</ref>

<ref name=arv>{{cite journal
 | last1 = Arora
 | first1 = Sanjeev
 | author1-link = Sanjeev Arora
 | last2 = Rao
 | first2 = Satish
 | author2-link = Satish Rao
 | last3 = Vazirani
 | first3 = Umesh
 | author3-link = Umesh Vazirani
 | doi = 10.1145/1502793.1502794
 | issue = 2
 | journal = Journal of the ACM
 | mr = 2535878
 | page = Art. 5, 37
 | title = Expander flows, geometric embeddings and graph partitioning
 | url = https://www.cs.princeton.edu/~arora/pubs/arvfull.pdf
 | volume = 56
 | year = 2009
 | access-date = 2024-01-29
 | archive-date = 2024-06-16
 | archive-url = https://web.archive.org/web/20240616063018/https://www.cs.princeton.edu/~arora/pubs/arvfull.pdf
 | dead-url = no
 }}</ref>

<ref name=bfhv>{{cite journal
 | last1 = Blin | first1 = Guillaume
 | last2 = Fertin | first2 = Guillaume
 | last3 = Hermelin | first3 = Danny
 | last4 = Vialette | first4 = Stéphane
 | doi = 10.1016/j.jda.2008.03.004 | doi-access = free
 | issue = 4
 | journal = Journal of Discrete Algorithms
 | mr = 2463425
 | pages = 618–626
 | title = Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
 | volume = 6
 | year = 2008}}</ref>

<ref name=bfkkt>{{cite journal
 | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender
 | last2 = Fomin | first2 = Fedor V.
 | last3 = Koster | first3 = Arie M. C. A.
 | last4 = Kratsch | first4 = Dieter
 | last5 = Thilikos | first5 = Dimitrios M.
 | doi = 10.1007/s00224-011-9312-0
 | issue = 3
 | journal = Theory of Computing Systems
 | mr = 2885638
 | pages = 420–432
 | title = A note on exact algorithms for vertex ordering problems on graphs
 | volume = 50
 | year = 2012| hdl = 1956/4556
 | s2cid = 9967521 | hdl-access = free
 }}</ref>

<ref name=chung>{{cite journal
 | last = Chung
 | first = Fan R. K.
 | author-link = Fan Chung
 | doi = 10.1137/0606026
 | issue = 2
 | journal = SIAM Journal on Algebraic and Discrete Methods
 | mr = 778007
 | pages = 268–277
 | title = On the cutwidth and the topological bandwidth of a tree
 | url = https://mathweb.ucsd.edu/~fan/mypaps/fanpap/66cutwidth.pdf
 | volume = 6
 | year = 1985
 | access-date = 2024-01-29
 | archive-date = 2024-04-23
 | archive-url = https://web.archive.org/web/20240423184553/https://mathweb.ucsd.edu/~fan/mypaps/fanpap/66cutwidth.pdf
 | dead-url = no
 }}</ref>

<ref name=chusey>{{cite journal
 | last1 = Chung
 | first1 = F. R. K.
 | last2 = Seymour
 | first2 = P. D.
 | doi = 10.1016/0012-365X(89)90083-6
 | issue = 1-3
 | journal = Discrete Mathematics
 | mr = 1001391
 | pages = 113–119
 | title = Graphs with small bandwidth and cutwidth
 | url = https://mathweb.ucsd.edu/~fan/mypaps/fanpap/109bandwidth.pdf
 | volume = 75
 | year = 1989
 | access-date = 2024-01-29
 | archive-date = 2024-01-30
 | archive-url = https://web.archive.org/web/20240130045550/https://mathweb.ucsd.edu/~fan/mypaps/fanpap/109bandwidth.pdf
 | dead-url = no
 }}</ref>

<ref name=djivrt>{{cite journal
 | last1 = Djidjev | first1 = Hristo N.
 | last2 = Vrt'o | first2 = Imrich
 | doi = 10.7155/jgaa.00069 | doi-access = free
 | issue = 3
 | journal = Journal of Graph Algorithms and Applications
 | mr = 2112230
 | pages = 245–251
 | title = Crossing numbers and cutwidths
 | volume = 7
 | year = 2003}}</ref>

<ref name=dps>{{cite journal
 | last1 = Díaz
 | first1 = Josep
 | last2 = Petit
 | first2 = Jordi
 | last3 = Serna
 | first3 = Maria
 | date = September 2002
 | doi = 10.1145/568522.568523
 | issue = 3
 | journal = ACM Computing Surveys
 | pages = 313–356
 | title = A survey of graph layout problems
 | url = https://www.cs.upc.edu/~diaz/papersd/surveylay.pdf
 | volume = 34
 }}{{Dead link}}</ref>

<ref name=flmrs>{{cite conference
 | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
 | last2 = Lokshtanov | first2 = Daniel
 | last3 = Misra | first3 = Neeldhara
 | last4 = Rosamond | first4 = Frances A. | author4-link = Frances A. Rosamond
 | last5 = Saurabh | first5 = Saket
 | editor1-last = Hong | editor1-first = Seok-Hee 
 | editor2-last = Nagamochi | editor2-first = Hiroshi
 | editor3-last = Fukunaga | editor3-first = Takuro
 | doi = 10.1007/978-3-540-92182-0_28
 | pages = 294–305
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008, Proceedings
 | volume = 5369
 | year = 2008}}</ref>

<ref name=fotpra>{{cite journal
 | last1 = Fotouhi | first1 = Farshad
 | last2 = Pramanik | first2 = Sakti
 | doi = 10.1016/0020-0190(91)90070-X
 | issue = 5
 | journal = Information Processing Letters
 | mr = 1114421
 | pages = 271–275
 | title = Problem of optimizing the number of block accesses in performing relational join is NP-hard
 | url = https://archive.org/details/sim_information-processing-letters_1991-06-14_38_5/page/n48 | volume = 38
 | year = 1991}}</ref>

<ref name=gprtw>{{cite journal
 | last1 = Giannopoulou
 | first1 = Archontia C.
 | last2 = Pilipczuk
 | first2 = Jean-Florent, Michałand Raymond
 | last3 = Thilikos
 | first3 = Dimitrios M.
 | last4 = Wrochna
 | first4 = Marcin
 | doi = 10.1007/s00453-018-0424-7
 | issue = 2
 | journal = Algorithmica
 | mr = 3910081
 | pages = 557–588
 | title = Cutwidth: obstructions and algorithmic aspects
 | url = http://users.uoa.gr/~sedthilk/papers/cutobs.pdf
 | volume = 81
 | year = 2019
 | access-date = 2024-01-29
 | archive-date = 2024-01-30
 | archive-url = https://web.archive.org/web/20240130045548/http://users.uoa.gr/~sedthilk/papers/cutobs.pdf
 | dead-url = no
 }}</ref>

<ref name=klmu>{{cite journal
 | last1 = Kayaaslan | first1 = Enver
 | last2 = Lambert | first2 = Thomas
 | last3 = Marchal | first3 = Loris
 | last4 = Uçar | first4 = Bora
 | doi = 10.1016/j.tcs.2017.09.037 | doi-access = free
 | journal = Theoretical Computer Science
 | mr = 3734396
 | pages = 1–23
 | title = Scheduling series-parallel task graphs to minimize peak memory
 | volume = 707
 | year = 2018}}</ref>

<ref name=korsol>{{cite journal
 | last1 = Korach | first1 = Ephraim
 | last2 = Solel | first2 = Nir
 | doi = 10.1016/0166-218X(93)90171-J | doi-access = free
 | issue = 1
 | journal = Discrete Applied Mathematics
 | mr = 1218045
 | pages = 97–101
 | title = Tree-width, path-width, and cutwidth
 | url = https://archive.org/details/sim_discrete-applied-mathematics_1993-05-06_43_1/page/n104 | volume = 43
 | year = 1993}}</ref>

<ref name=leirao>{{cite journal
 | last1 = Leighton | first1 = Tom 
 | last2 = Rao | first2 = Satish 
 | doi = 10.1145/331524.331526 | doi-access = free
 | issue = 6
 | journal = Journal of the ACM
 | mr = 1753034
 | pages = 787–832
 | title = Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
 | volume = 46
 | year = 1999}}</ref>

<ref name=maksud>{{cite journal
 | last1 = Makedon | first1 = Fillia 
 | last2 = Sudborough | first2 = Ivan Hal
 | doi = 10.1016/0166-218X(89)90016-4 | doi-access = free
 | issue = 3
 | journal = Discrete Applied Mathematics
 | mr = 996137
 | pages = 243–265
 | title = On minimizing width in linear layouts
 | url = https://archive.org/details/sim_discrete-applied-mathematics_1989-06_23_3/page/243 | volume = 23
 | year = 1989}}</ref>

<ref name=monsud>{{cite journal
 | last1 = Monien | first1 = B.
 | last2 = Sudborough | first2 = I. H.
 | doi = 10.1016/0304-3975(88)90028-X | doi-access = free
 | issue = 1-3
 | journal = Theoretical Computer Science
 | mr = 963264
 | pages = 209–229
 | title = Min cut is NP-complete for edge weighted trees
 | url = https://archive.org/details/sim_theoretical-computer-science_1988-06_58_1-3/page/209 | volume = 58
 | year = 1988}}</ref>

<ref name=morwoo>{{cite journal
 | last1 = Morin | first1 = Pat 
 | last2 = Wood | first2 = David R. 
 | doi = 10.7155/jgaa.00095 | doi-access = free
 | issue = 3
 | journal = Journal of Graph Algorithms and Applications
 | mr = 2176967
 | pages = 357–366
 | title = Three-dimensional 1-bend graph drawings
 | volume = 8
 | year = 2004}}</ref>

<ref name=seytho>{{cite journal
 | last1 = Seymour | first1 = Paul D. 
 | last2 = Thomas | first2 = Robin
 | doi = 10.1007/BF01215352
 | issue = 2
 | journal = Combinatorica
 | pages = 217–241
 | title = Call routing and the ratcatcher
 | url = https://archive.org/details/sim_combinatorica_1994_14_2/page/217 | volume = 14
 | year = 1994}}</ref>

<ref name=stohr>{{cite journal
 | last = Stöhr | first = Elena
 | doi = 10.1016/0890-5401(88)90036-3 | doi-access = free
 | issue = 2
 | journal = Information and Computation
 | mr = 968104
 | pages = 155–162
 | title = A trade-off between page number and page width of book embeddings of graphs
 | volume = 79
 | year = 1988}}</ref>

<ref name=tsb>{{cite journal
 | last1 = Thilikos
 | first1 = Dimitrios M.
 | last2 = Serna
 | first2 = Maria
 | last3 = Bodlaender
 | first3 = Hans L.
 | doi = 10.1016/j.jalgor.2004.12.001
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 2146375
 | pages = 1–24
 | title = Cutwidth I: A linear time fixed parameter algorithm
 | url = http://users.uoa.gr/~sedthilk/papers/cut.pdf
 | volume = 56
 | year = 2005
 | access-date = 2024-01-29
 | archive-date = 2024-05-02
 | archive-url = https://web.archive.org/web/20240502143528/http://users.uoa.gr/~sedthilk/papers/cut.pdf
 | dead-url = no
 }}</ref>

<ref name=wapl>{{cite journal
 | last1 = Wu | first1 = Yu
 | last2 = Austrin | first2 = Per
 | last3 = Pitassi | first3 = Toniann 
 | last4 = Liu | first4 = David
 | doi = 10.1613/jair.4030 | doi-access = free
 | journal = Journal of Artificial Intelligence Research
 | mr = 3195329
 | pages = 569–600
 | title = Inapproximability of treewidth, one-shot pebbling, and related layout problems
 | volume = 49
 | year = 2014}}</ref>

<ref name=yannakakis>{{cite journal
 | last = Yannakakis | first = Mihalis 
 | doi = 10.1145/4221.4228 | doi-access = free
 | issue = 4
 | journal = Journal of the ACM
 | mr = 810346
 | pages = 950–988
 | title = A polynomial algorithm for the min-cut linear arrangement of trees
 | volume = 32
 | year = 1985}}</ref>

}}

[[Category:图论]]
[[Category:图常量]]