图论中,图的刻宽(carving width)是由图定义的数,描述了图顶点的层次聚类中,分隔聚类的边数。

定义与例子

编辑

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

刻宽恰为1的图是匹配。刻宽为2的图是径图循环图的不交并形成的图。刻宽为3的图是次立方部分2树,这意味着其最大度为3,并是系列平行图的子图。其他图的刻宽至少为4。[2]

计算复杂度

编辑

刻宽的计算总的来说是NP困难的,但在平面图中可用多项式时间计算。[1]其近似率与平衡的近似率相仿,[3]目前的最佳近似率为 [4]它还是固定参数可解的:对定值 ,测试刻宽是否不大于k,若是,则找到实现此宽度的分层聚类可在线性时间内完成。[5]总的来说,在n个顶点、m条边的重图上精确计算刻宽可在 的时间内完成。[6]

相关参数

编辑

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

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

参考文献

编辑
  1. ^ 1.0 1.1 Seymour, Paul D.; Thomas, Robin, Call routing and the ratcatcher, Combinatorica, 1994, 14 (2): 217–241, S2CID 7508434, doi:10.1007/BF01215352 
  2. ^ Belmonte, Rémy; van 't Hof, Pim; Kamiński, Marcin; Paulusma, Daniël; Thilikos, Dimitrios M., Characterizing graphs of small carving-width, Discrete Applied Mathematics, 2013, 161 (13–14): 1888–1893, MR 3056995, doi:10.1016/j.dam.2013.02.036  
  3. ^ Khuller, Samir; Raghavachari, Balaji; Young, Neal, Designing multi-commodity flow trees, Information Processing Letters, April 1994, 50 (1): 49–55, arXiv:cs/0205077 , doi:10.1016/0020-0190(94)90044-2 
  4. ^ Arora, Sanjeev; Rao, Satish; Vazirani, Umesh, Expander flows, geometric embeddings and graph partitioning (PDF), Journal of the ACM, 2009, 56 (2): A5:1–A5:37 [2024-01-30], MR 2535878, S2CID 263871111, doi:10.1145/1502793.1502794, (原始内容存档 (PDF)于2022-12-07) 
  5. ^ 5.0 5.1 Thilikos, Dimitrios M.; Serna, Maria J.; Bodlaender, Hans L., Constructive linear time algorithms for small cutwidth and carving-width, Lee, D. T.; Teng, Shang-Hua (编), Algorithms and Computation, 11th International Conference, ISAAC 2000, Taipei, Taiwan, December 18-20, 2000, Proceedings, Lecture Notes in Computer Science 1969, Springer: 192–203, 2000, ISBN 978-3-540-41255-7, doi:10.1007/3-540-40996-3_17 
  6. ^ Oum, Sang-il, Computing rank-width exactly, Information Processing Letters, 2009, 109 (13): 745–748, CiteSeerX 10.1.1.483.6708 , MR 2527717, doi:10.1016/j.ipl.2009.03.018 
  7. ^ 7.0 7.1 Eppstein, David, The effect of planarization on width, Journal of Graph Algorithms & Applications, 2018, 22 (3): 461–481, S2CID 28517765, arXiv:1708.05155 , doi:10.7155/jgaa.00468