径宽

来自testwiki
跳转到导航 跳转到搜索

图论中，图G的径分解（path decomposition）是G的“加粗”路径图表示，[1]G的径宽（pathwidth）是衡量形成G的路径被加粗的程度。更正式地说，径分解是G的顶点子集序列，使每条边的端点出现在某一子集中，并使每个顶点都出现在子集连续子序列中，[2]径宽等于这样的分解中最大集的大小减一。 径宽也叫做区间厚度（interval thickness，等于G的区间父图中的最大团大小减一）、顶点分隔数（vertex separation number）或结点搜索数（node searching number）。[3]

径宽与径分解同树宽、树分解关系密切，在图子式理论中起关键作用：在图子式下封闭、不含所有森林的图族可描述为径宽有界，[2]子式闭图族的一般结构理论中出现的“涡”（vortex）的径宽也有界。[4]径宽与径宽有界图在超大规模集成电路设计、图绘制、计算语言学等领域也有应用。

计算任意图的径宽、甚至精确近似径宽都是NP困难的。[5][6]不过，这问题是固定参数可解的：测试图的径宽是否为k，耗时与图的大小呈线性关系，而与k呈上指数关系。[7]另外，对树之类的特殊图，径宽可在多项式时间内算得，而不依赖于k。Template:Sfnp[8] 对图的径分解使用动态规划，可以将图算法中很多问题在径宽有界图上高效解决。[9]径分解也可测量树宽有界图上动态规划算法的空间复杂度。[10]

定义

径宽为2的例图G，其径分解宽度为2。图像下半部是相同的图与径分解，添加了颜色以示强调。（本例改编自Template:Harvp，添加了记号）

Template:Harvs在图子式系列论文的第一篇中，将图G的径分解定义为G的顶点子集Xi序列，满足两条属性：

  1. 对G中每条边，存在i使边的两端点都属于子集Xi；
  2. ∀i≤j≤k, Xi∩Xk⊆Xj.

第二条性质等价于要求包含任意特定顶点的子集构成整个序列的连续子列。用系列论文后期的话来说，径分解是树分解(X, T)，其中分解的底树T是路径图。 径分解的宽度与树分解类似，是maxi|Xi|−1，G的径宽是G的径分解的最小宽度。在径宽的大多数应用中，Xi的大小减不减一没什么差别，主要是为了使路径图的径宽等于1。

其他特征

如Template:Harvtxt所描述的，径宽可用许多等价方法表征。

粘合序列

径分解可表述为图Gi的序列，找到来自序列中连续图的顶点对，并将图粘合在一起，所有粘合的结果就是G。在径分解的第一个定义中，图Gi可看作是集合Xi的诱导子图，连续（successive）诱导子图中的两顶点被G中相同顶点诱导时，就会被粘在一起；反之，可以把集合Xi恢复为图Gi的顶点集。则径分解的宽度比某一图Gi的最大顶点数少1。[2]

区间厚度

径宽为2的区间图，而4个最大团ABC、ACD、CDE、CDF的大小为3。

任意图G的径宽等于含G（以G为子图）的区间图的最小团数减一。[11]即，对G的每种径分解，都能找到G的区间子图；对G的每个区间父图，都能找到G的径分解，使分解的宽度比区间图团数小1。

假设给出了G的径分解。则可将分解的结点表为直线上的点（按路径顺序），并将每个顶点v表示为以这些点为端点的闭区间。这样，包含v的径分解结点就对应v在区间中的代表点。G顶点形成的区间交图是包含G的区间图，其最大团由包含代表点的区间集给出，大小比G的径宽大1。

设G是某区间图的子图，团数p+1，则G有宽p的径分解，其结点由区间图的最大团给出。例如，图中的区间图及其区间表示的径分解有5个结点，分别对应5个最大团ABC、ACD、CDE、CDF、FG；最大团大小为3，这径分解的宽度为2。 径宽与区间厚度之间的等价关系同树宽与弦图（给定图是弦图的子图）的最小团数（减一）的等价关系非常相似。区间图是弦图的特例，弦图可表为共同树的子树的交图，这类似于区间图是路径子径的交图。

顶点分隔数

设图G的顶点是线性有序的。则，G的顶点分隔数是满足下列条件的最小数s：对顶点v，最多s个顶点在排序中先于v，但有v或更靠后的顶点相邻。 G的顶点分隔数是G的任意线性排序的最小顶点分隔数。顶点分隔数由Template:Harvtxt定义，等于G的径宽。[12] 这源于前述的与区间图团数的等价关系：若G是区间图I的子图，并以所有区间端点都分离的方式表示（如图所示），则I的区间左端点排序的顶点分隔数比I的团数小1。反过来，从G的线性排序可推导出一种区间表示：顶点v的区间左端点是其在排序中的位置，右端点是v在排序中最后一个邻居的位置。

结点搜索数

图上的结点搜索策略是追逃对策的一种形式，当中一组搜索者合作追踪藏在图中的逃犯。搜索者被置于图的顶点上，逃犯可能在任意边上，位置与移动对搜索者不可见。每个回合中，搜索者的部分或全部可从顶点移动到另一顶点（任意移动，不必沿边），逃犯可以沿不经过搜索者顶点的任意路径移动。逃犯所在边的两端点都被搜索者占据时，就被抓获。图的结点搜索数是必然能抓到逃犯的最少搜索者数。如Template:Harvtxt所示，图的结点搜索数等于其区间厚度。搜索者的最优策略是不断移动搜索者，使他们在连续回合中形成具有最小顶点分隔数的线性排序的分隔集。

界

毛虫树，径宽为1的最大图。

径宽为k的n顶点图至多有k(n−k+k−12)条边，是最大k径宽图（即径宽为k、无论怎样添加边都必改变径宽的图）的边数。径宽为k的最大图要么是k径图要么是k毛虫图，它们是两种特殊的k树。k树是恰有n−k个最大团（含k+1个顶点）的弦图；在本身不是(k+1)团的k树中，每个最大团要么将图分隔成多个部分，要么包含单个叶顶点（只属于一个最大团的顶点）。k径图是至少有两叶的k树，k毛虫图是可分割维k径与一组k叶的k树，其中每片叶还与k径中的独立k团相邻。径宽为1的最大图是毛虫树。[13]

由于径分解是树分解的特例，径宽不小于树宽，且不大于割宽，即在图顶点的最优线性排列中，前后顶点组之间割边的最小数。这是因为，顶点分隔数即前后顶点组的邻接数不大于割边数。[14]出于类似原因，割宽不大于径宽乘顶点的最大度。[15]

任意n顶点森林都有径宽O(log⁡n)。[16]例如，对一个森林，总能找到恒定多的顶点，使得去掉它们后形成至多有2n3个顶点的两片子森林。如此递归地分隔子森林，将分隔顶点置于两者之间，形成的线性排列具有对数顶点搜索数。此技术用于树分解时，可知，若n顶点图G的树宽为t，则G的径宽是O(tlog⁡n)。[17]由于外平面图、系列并行图、哈林图的树宽都有界，它们的径宽最多为对数的。

此外，径宽还通过线图，同团宽与割宽有关系。G的边在其线图L(G)中都有对应的顶点，当G中相应的两边有共同端点时，L(G)中的两顶点就是相邻的。当且仅当图族的线图的线性团宽（用邻接1个新顶点的操作取代了团宽的不交并操作）有界，图族的径宽有界。[18]若某3及以上个顶点的连通图的最大度为3，则其割宽等于线图的顶点分隔数。[19]

平面图的径宽最多与顶点数的平方根成正比。[20]找到具有这种宽度的径分解，一种方法是（与上述森林的对数宽径分解类似）用平面分隔定理找到O(n)个顶点的集合，其将图分隔为至多有2n3个顶点的两个子图，如此递归地分隔子图，最后将两子图的递归径分解连接起来。同样的技术也适用于类似分离器定理成立的任何一类图。[21]与平面图一样，任何固定的子式闭图族中的图都有大小为O(n)的分隔子，[22]因此此类图族中图的径宽也是O(n)。对某类平面图，图的径宽与其对偶图的径宽必须在一常数因子范围内，对于双连通外平面图[23]与多面体图[24]，这种形式的边界是已知的。2连通平面图的对偶图的径宽小于线图的径宽。[25]至于在其他情形下，平面图径宽与对偶图径宽是否总相差某常数因子，仍是未知的。

在某些类的图中，径宽与树宽总相等。已证明的有余图、[26]置换图、[27]可比图之补、[28]区间序的可比图。[29]

Template:Unsolved 在立方图中，或更广义地在任何最大顶点度为3的图中，径宽不大于n6+o(n)，其中n是顶点数。存在径宽为0.082n的立方图，但如何缩小这下界与上界n6之间的差距，目前还不得而知。[30]

计算径分解

确定给定图的径宽是否大于k的问题是NP完全的（k也是输入）。[5]计算任意n顶点图径宽的最坏情形的最优时间边界为O(2nnc)，c是常数。[31]不过，已经有几种算法可在径宽较小、输入图类别有限或近似的情形下更高效地计算径分解。

固定参数可解

径宽是固定参数可解的：对任意常数k，都可测试径宽是否大于k，若不大于k，则在线性时间内找到宽k的径分解。[7]一般来说，这类算法分两阶段运行。第一阶段，假设图的径宽为k，以找到并非最优的径分解或树分解，宽度可作为k的函数而变为约束。第二阶段，对这分解运用动态规划算法，以找到最优分解。然而，已知的这类算法的时间界限是k2的指数级，除了最小的k外，都是不切实际的。[32]对于k=2的情形，Template:Harvtxt给出了基于2径宽图的结构分解的精确限行时间算法。

特殊图类

Template:Harvp调查了计算各种特殊图类的径宽的复杂性。若图G是有界度图、[33]平面图、[33]有界度平面图、[33]弦图、[34]弦多米诺、[35]可比图之补、[28]二分距离遗传图[36]，确定图G的径宽是否最大是k的问题仍是NP完全的。对于包含二分距离遗传图的图族（二分图、弦二分图、距离遗传图、循环图之类），也是NP完全的。[36]

不过，对于树与森林，径宽可在线性时间内算得。[8]对树宽有界图族（系列并行图、外平面图、哈林图）[7]、裂图[37]、弦图之补[38]、置换图[27]、余图[26]、圆弧图[39]、区间序的可比图[29]、区间图，也可在多项式时间内计算出来。这种情形下，径宽比覆盖图的区间表示中所有点的最大区间数小1。

近似算法

将图的径宽近似到加常数范围内，是NP难的。[6] 已知近似率最佳的多项式时间近似算法是O((log⁡n)3/2)。[40] 关于计算径宽的早期近似算法，见Template:Harvtxt与Template:Harvtxt；关于受限图类的近似计算，见Template:Harvtxt。

图子式

图G的子式是由G通过收缩边、移除边、移除顶点得到的另一张图。图子式有深奥的理论，其中几个重要结果涉及径宽。

排除森林

若图族F对取子式封闭（即F成员的子式还在F中），则由罗伯森–西摩定理，F的特征是在禁子式有限集X中没有任何子式。[41]例如，瓦格纳定理指出，平面图是既没有完整图K5也没有完全二分图K3, 3作为子式的图。很多时候，F的性质与X的性质密切相关，此类的第一个结果由Template:Harvtxt提出，[2]将有界径宽与禁子式族中森林的存在联系起来。具体来说，若存在常数p使F中图的径宽不大于p，则称图族F具有有界径宽。那么，当且仅当F的禁子式集X至少包括一个森林时，子式闭族F具有有界的径宽。

从一个方向来看，这结果很容易证明：若X不含森林，则“无X子式图”的径宽便无界。因为这时，无X子式图将包含所有森林，特别是包括完美二叉树。而一棵2k+1层的完美二叉树的径宽为k，所以这时无X子式图的径宽无解。从另一方向看，若X包含n顶点森林，则无X子式图的径宽不大于n−2。[42]

径宽有界的障碍

径宽为1的图的禁子式。

径宽不大于p的性质本身对取子式封闭：若G的径分解宽度不大于p，则从G中删去任何边，同一径分解仍有效，且可以从G及其径分解中删去任意顶点而不增加宽度。同样，通过合并表示收缩后边的两端点的子径，也可在收缩边时不增加分解宽度。因此，径宽至多为p的图可用排除子式的集合Xp描述。[41][43]

虽然Xp必然包括森林，但并不是说Xp中的所有图都是森林：例如，X1包含2张图，一个7顶点树与三角K3。而Xp中的树集可以精确描述：它们是Xp−1中三棵树通过边，连接新的根顶点与3棵小树中任意顶点而形成的树。例如，X1中的7顶点树就是这样由X0中的2顶点树（一条边）组成的。基于这种构造，可以证明Xp中的禁子式数至少为(p!)2。[43]已计算出2径宽图的完备禁子式集X2，其中包含110个图。[44]

结构理论

子式闭图族的图结构定理指出，对任意图族F，其中的图可分解为能嵌入到亏格有界曲面上的图的团和，且团和的每个分量都有有界多的顶点（apex）与涡（vortex）。这里的顶点可能与其组分中任何顶点相邻，涡是径宽有界图，粘合到某组分的亏格有界嵌入的面上。涡所嵌入面周围的顶点的循环排序必须与涡的径分解相容，即，打破循环、形成线性排序必然产生顶点分隔数有界的排序。[4]这一理论中，径宽与任意子式闭图族密切相关，具有重要的算法应用。[45]

应用

超大规模集成电路

超大规模集成电路设计中，顶点分隔问题最初是将电路分为子系统的方法，子系统边界有少量元件。[33]

Template:Harvtxt使用区间厚度模拟VLSI一维布局所需的轨道数，此布局由网络系统相互连接的模块组成。在他们的模型中，顶点代表网，若两网都连接到同一模块，就将两顶点由边相连；也就是说，若将模块与网视作超图的结点与超边，则由它们形成的图就是超图的线图。这超图的区间表示与着色描述了沿水平轨道（一种颜色对应一条轨道）系统的网的排列，使模块可沿轨道以线性顺序排列，并连接到相应的网。区间图都是完美图[46]，表明这类最佳排列中，所需颜色数等于网图的区间完备化的团数。

门矩阵布局[47]是一种用于布尔逻辑电路的CMOS VLSI布局。当中，信号沿“线”（垂直线段）传播，而电路的每个门则由沿水平线段的一系列器件特征构成。因此，代表门的水平线段须与代表门输入输出的线路的垂直线段交叉。与Template:Harvtxt的布局类似，通过计算以线路为顶点，以共享同一门的线对为边的图的径宽，可以找到使排列线路的垂直轨道数最小的布局。[48]这种算法方法也可为可编程逻辑阵列的折叠问题建模。[49]

图绘制

径宽在图绘制中有多个应用：

  • 给定交叉数的最小图的径宽受交叉数函数的约束。[50]
  • 树的顶点可画在多少条平行线上而边不交（根据对相邻顶点在线序列上摆放方式的各种自然限制），与树的径宽成正比。[51]
  • 图G的k交叉h层绘图是将G的顶点放置在h条水平线上，边在其间以单调多边形路径排列，使得最多有k处交叉。具有这种绘制的图的径宽由h与k的函数约束。于是，h、k为常值时，可在线性时间内确定图是都具有k交叉h层绘制。[52]
  • n顶点、径宽为p的图可嵌入3维格p×p×n，使得边（表为格点间的直线段）不交。于是，径宽有界图具有此种线性体积嵌入。[53]

编译器设计

高级语言的编译过程中，径宽见于重排直线代码序列（即无控制流分支或循环的代码）问题，使代码算得的所有值都可放在寄存器中，而不必溢出到主内存中。这种应用中，我们将待编译代码表为有向无环图，其中结点是代码的输入输出值。这个DAG中，结点x到结点y的边表示x值是操作了y的输入之一。此DAG的顶点的拓扑排序表示代码的有效重排，在给定排序中评估代码所需的寄存器数由排序的顶点分隔数给出。[54]

对表示寄存器数的任意定值w，可在限行时间内确定一段直线代码能否重排，以便用不多于w个寄存器求值。若拓扑排序的顶点分隔数最多为w，则所有排序中的最小顶点分隔也不会更大，于是忽略DAG方向形成的无向图的径宽不大于w。可用已知的固定参数可解算法计算径宽，若是，则可在假设w为常数的线性时间内找到无向图的径分解。找到径分解，就可用动态规划，在线性时间内找到宽w的拓扑排序。[54]

语言学

Template:Harvtxt描述了径宽在自然语言处理中的应用。句子被建模为图，顶点表示词，边表示词之间的关系。例如，若形容词修饰了名词，则图中这两个词之间就会有一条边。Kornai和Tuza认为，由于人类的短时记忆能力有限，[55]这种图的径宽一定有界（更具体地说，他们认为是6），否则人类将无法正确解析语言。

指数算法

图算法中的很多问题都可通过对径分解进行动态规划，在径宽较小的图上高效解决。[9]例如，若给定n顶点图G的顶点的线性排序，就有可能在O(2wn)的时间内找到G的最大独立集。[30]在径宽有界图上，这种方法会产生以径宽为参数的固定参数可解算法。[48]这种结果在文献中不常见，因为已经包含在以树宽为参数的类似算法；然而，即使在基于树宽的动态规划算法中，径宽也会出现衡量算法空间复杂度的过程中。[10]

同样的动态规划方法也可用于径宽无界图，产生以指数时间解决无参图问题的算法。例如，将这种方法与立方图径宽为n6+o(n)的事实相结合，可以发现在立方图中，最大支配集的构造耗时O(2n6+o(n))，比以往方法更快。[30]类似方法还可改进立方图中最大割与最小支配集问题的指数时间算法，[30]及其他一些NP难优化问题的指数时间算法。[56]

另见

注释

Template:Reflist

参考文献

Template:Refbegin

Template:Refend

  1. ↑ Template:Harvtxt.
  2. ↑ 2.0 2.1 2.2 2.3 Template:Harvtxt.
  3. ↑ Template:Harvtxt.
  4. ↑ 4.0 4.1 Template:Harvtxt.
  5. ↑ 5.0 5.1 Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.
  6. ↑ 6.0 6.1 Template:Harvtxt.
  7. ↑ 7.0 7.1 7.2 Template:Harvtxt; Template:Harvtxt
  8. ↑ 8.0 8.1 Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.
  9. ↑ 9.0 9.1 Template:Harvtxt.
  10. ↑ 10.0 10.1 Template:Harvtxt.
  11. ↑ Template:Harvtxt, Theorem 29, p. 13.
  12. ↑ Template:Harvtxt; Template:Harvtxt, Theorem 51.
  13. ↑ Template:Harvtxt.
  14. ↑ Template:Harvtxt, Lemma 3 p.99; Template:Harvtxt, Theorem 47, p. 24.
  15. ↑ Template:Harvtxt, Lemma 1, p. 99; Template:Harvtxt, Theorem 49, p. 24.
  16. ↑ Template:Harvtxt, Theorem 5, p. 99; Template:Harvtxt, Theorem 66, p. 30. Template:Harvtxt为n顶点森林的径宽提供了更紧的上界：log3(2n+1)。
  17. ↑ Template:Harvtxt, Theorem 6, p. 100; Template:Harvtxt, Corollary 24, p.10.
  18. ↑ Template:Harvtxt.
  19. ↑ Template:Harvtxt.
  20. ↑ Template:Harvtxt, Corollary 23, p. 10.
  21. ↑ Template:Harvtxt, Theorem 20, p. 9.
  22. ↑ Template:Harvtxt.
  23. ↑ Template:Harvtxt; Template:Harvtxt.
  24. ↑ Template:Harvtxt; Template:Harvtxt.
  25. ↑ Template:Harvtxt.
  26. ↑ 26.0 26.1 Template:Harvtxt.
  27. ↑ 27.0 27.1 Template:Harvtxt.
  28. ↑ 28.0 28.1 Template:Harvtxt.
  29. ↑ 29.0 29.1 Template:Harvtxt.
  30. ↑ 30.0 30.1 30.2 30.3 Template:Harvtxt.
  31. ↑ Template:Harvtxt.
  32. ↑ Template:Harvtxt, p.12.
  33. ↑ 33.0 33.1 33.2 33.3 Template:Harvtxt.
  34. ↑ Template:Harvtxt.
  35. ↑ Template:Harvtxt. 弦多米诺是顶点都属于至多2个最大团的弦图。
  36. ↑ 36.0 36.1 Template:Harvtxt.
  37. ↑ Template:Harvtxt; Template:Harvtxt.
  38. ↑ Template:Harvtxt将此成果归功于Ton Kloks的博士论文（1993）；Garbe对区间序的可比图的多项式时间算法推广了结果，而弦图属于此类可比图。
  39. ↑ Template:Harvtxt.
  40. ↑ Template:Harvtxt.
  41. ↑ 41.0 41.1 Template:Harvtxt.
  42. ↑ Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.
  43. ↑ 43.0 43.1 Template:Harvtxt; Template:Harvtxt; Template:Harvtxt, p. 8.
  44. ↑ Template:Harvtxt.
  45. ↑ Template:Harvtxt.
  46. ↑ Template:Harvtxt.
  47. ↑ Template:Harvtxt.
  48. ↑ 48.0 48.1 Template:Harvtxt.
  49. ↑ Template:Harvtxt; Template:Harvtxt.
  50. ↑ Template:Harvtxt.
  51. ↑ Template:Harvtxt.
  52. ↑ Template:Harvtxt.
  53. ↑ Template:Harvtxt.
  54. ↑ 54.0 54.1 Template:Harvtxt.
  55. ↑ Template:Harvtxt.
  56. ↑ Template:Harvtxt; Template:Harvtxt.
检索自“https://zh.wiki.beta.math.wmflabs.org/w/index.php?title=径宽&oldid=13940”