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

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

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

刻宽恰为1的图是[[匹配 (图论)|匹配]]。刻宽为2的图是[[道路 (图论)|径图]]与[[循环图]]的不交并形成的图。刻宽为3的图是次立方部分2树，这意味着其最大度为3，并是[[系列平行图]]的子图。其他图的刻宽至少为4。{{r|bhkpt}}

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

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

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

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

<ref name=arv>{{citation
 | 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 = A5:1–A5:37
 | title = Expander flows, geometric embeddings and graph partitioning
 | url = https://people.eecs.berkeley.edu/~vazirani/pubs/arvfull.pdf
 | volume = 56
 | year = 2009
 | s2cid = 263871111
 | accessdate = 2024-01-30
 | archive-date = 2022-12-07
 | archive-url = https://web.archive.org/web/20221207175519/https://people.eecs.berkeley.edu/~vazirani/pubs/arvfull.pdf
 | dead-url = no
 }}</ref>

<ref name=bhkpt>{{citation
 | last1 = Belmonte | first1 = Rémy
 | last2 = van 't Hof | first2 = Pim
 | last3 = Kamiński | first3 = Marcin
 | last4 = Paulusma | first4 = Daniël
 | last5 = Thilikos | first5 = Dimitrios M.
 | doi = 10.1016/j.dam.2013.02.036
 | issue = 13–14
 | journal = [[Discrete Applied Mathematics]]
 | mr = 3056995
 | pages = 1888–1893
 | title = Characterizing graphs of small carving-width
 | volume = 161
 | year = 2013| doi-access = free
 }}</ref>

<ref name=eppstein>{{citation
 | last = Eppstein | first = David | author-link = David Eppstein
 | doi = 10.7155/jgaa.00468
 | issue = 3
 | journal = Journal of Graph Algorithms & Applications
 | pages = 461–481
 | title = The effect of planarization on width
 | volume = 22
 | year = 2018| arxiv = 1708.05155
 | s2cid = 28517765 }}</ref>

<ref name=kry>{{citation
 | last1 = Khuller | first1 = Samir
 | last2 = Raghavachari | first2 = Balaji
 | last3 = Young | first3 = Neal
 | date = April 1994
 | doi = 10.1016/0020-0190(94)90044-2
 | issue = 1
 | journal = Information Processing Letters
 | pages = 49–55
 | title = Designing multi-commodity flow trees
 | volume = 50| arxiv = cs/0205077
 }}</ref>

<ref name=oum>{{citation
 | last = Oum | first = Sang-il
 | doi = 10.1016/j.ipl.2009.03.018
 | issue = 13
 | journal = Information Processing Letters
 | mr = 2527717
 | pages = 745–748
 | title = Computing rank-width exactly
 | volume = 109
 | year = 2009| citeseerx = 10.1.1.483.6708
 }}</ref>

<ref name=seytho>{{citation
 | last1 = Seymour | first1 = Paul D. | author1-link = Paul Seymour (mathematician)
 | last2 = Thomas | first2 = Robin
 | doi = 10.1007/BF01215352
 | issue = 2
 | journal = Combinatorica
 | pages = 217–241
 | title = Call routing and the ratcatcher
 | volume = 14
 | year = 1994| s2cid = 7508434 }}</ref>

<ref name=tsb>{{citation
 | last1 = Thilikos | first1 = Dimitrios M.
 | last2 = Serna | first2 = Maria J. | author2-link = Maria Serna
 | last3 = Bodlaender | first3 = Hans L. | author3-link = Hans L. Bodlaender
 | editor1-last = Lee | editor1-first = D. T.
 | editor2-last = Teng | editor2-first = Shang-Hua
 | contribution = Constructive linear time algorithms for small cutwidth and carving-width
 | doi = 10.1007/3-540-40996-3_17
 | pages = 192–203
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings
 | volume = 1969
 | isbn = 978-3-540-41255-7
 | year = 2000}}</ref>

}}

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