径宽 - 版本历史

吃卤煮的火烧：/* 径宽有界的障碍 */

2025-06-21T09:25:02Z

径宽有界的障碍

吃卤煮的火烧：/* 特殊图类 */

2025-06-21T09:23:31Z

特殊图类

吃卤煮的火烧：/* 界 */

2025-06-21T09:23:03Z

界

吃卤煮的火烧：/* 区间厚度 */

2025-06-21T09:20:37Z

区间厚度

吃卤煮的火烧：/* 定义 */

2025-06-21T09:18:00Z

定义

吃卤煮的火烧：/* 定义 */

2025-06-21T09:16:01Z

定义

2025年6月21日 (六) 09:06 吃卤煮的火烧

2025-06-21T09:06:42Z

2025年6月21日 (六) 09:06 吃卤煮的火烧

2025-06-21T09:06:11Z

2025年6月21日 (六) 09:05 吃卤煮的火烧

2025-06-21T09:05:27Z

2025年6月21日 (六) 09:04 吃卤煮的火烧

2025-06-21T09:04:52Z

显示更改

@@ 第78行： / 第78行： @@
 从一个方向来看，这结果很容易证明：若''X''不含森林，则“无''X''子式图”的径宽便无界。因为这时，无''X''子式图将包含所有森林，特别是包括[[二叉树#完美二叉树|完美二叉树]]。而一棵<math>2k+1</math>层的完美二叉树的径宽为''k''，所以这时无''X''子式图的径宽无解。从另一方向看，若''X''包含''n''顶点森林，则无''X''子式图的径宽不大于<math>n-2</math>。<ref>{{harvtxt|Bienstock|Robertson|Seymour|Thomas|1991}}; {{harvtxt|Diestel|1995}}; {{harvtxt|Cattell|Dinneen|Fellows|1996}}.</ref>
 ===径宽有界的障碍===
-[[File:Pathwidth-1 obstructions.svg|thumb|径宽为1的图的禁子式。]]
+[[文件:Pathwidth-1 obstructions.svg|thumb|径宽为1的图的禁子式。]]
 径宽不大于''p''的性质本身对取子式封闭：若''G''的径分解宽度不大于''p''，则从''G''中删去任何边，同一径分解仍有效，且可以从''G''及其径分解中删去任意顶点而不增加宽度。同样，通过合并表示收缩后边的两端点的子径，也可在收缩边时不增加分解宽度。因此，径宽至多为''p''的图可用排除子式的集合<math>X_p</math>描述。<ref name="gm20"/><ref name="obstructions">{{harvtxt|Kinnersley|1992}}; {{harvtxt|Takahashi|Ueno|Kajitani|1994}}; {{harvtxt|Bodlaender|1998}}, p. 8.</ref>

@@ 第61行： / 第61行： @@
 ===特殊图类===
-{{harvp|Bodlaender|1994}}调查了计算各种特殊图类的径宽的复杂性。若图''G''是有界度图、<ref name="ms88">{{harvtxt|Monien|Sudborough|1988}}.</ref>[[平面图]]、<ref name="ms88"/>有界度平面图、<ref name="ms88"/>[[弦图]]、<ref>{{harvtxt|Gustedt|1993}}.</ref>弦多米诺、<ref>{{harvtxt|Kloks|Kratsch|Müller|1995}}. 弦多米诺是顶点都属于至多2个最大团的弦图。</ref>[[可比图]]之[[补图|补]]、<ref name="hm94"/>[[二分图|二分]][[距离遗传图]]<ref name="kbmk">{{harvtxt|Kloks|Bodlaender|Müller|Kratsch|1993}}.</ref>，确定图''G''的径宽是否最大是''k''的问题仍是NP完全的。对于包含二分距离遗传图的图族（二分图、弦二分图、距离遗传图、[[循环图]]之类），也是NP完全的。<ref name="kbmk"/>
+Bodlaender (1994)调查了计算各种特殊图类的径宽的复杂性。若图''G''是有界度图、<ref name="ms88">{{harvtxt|Monien|Sudborough|1988}}.</ref>[[平面图]]、<ref name="ms88"/>有界度平面图、<ref name="ms88"/>[[弦图]]、<ref>{{harvtxt|Gustedt|1993}}.</ref>弦多米诺、<ref>{{harvtxt|Kloks|Kratsch|Müller|1995}}. 弦多米诺是顶点都属于至多2个最大团的弦图。</ref>[[可比图]]之[[补图|补]]、<ref name="hm94"/>[[二分图|二分]][[距离遗传图]]<ref name="kbmk">{{harvtxt|Kloks|Bodlaender|Müller|Kratsch|1993}}.</ref>，确定图''G''的径宽是否最大是''k''的问题仍是NP完全的。对于包含二分距离遗传图的图族（二分图、弦二分图、距离遗传图、[[循环图]]之类），也是NP完全的。<ref name="kbmk"/>
 不过，对于树与森林，径宽可在线性时间内算得。<ref name="tree-algs">{{harvtxt|Möhring|1990}}; {{harvtxt|Scheffler|1990}}; {{harvtxt|Ellis|Sudborough|Turner|1994}}; {{harvtxt|Peng|Ho|Hsu|Ko|1998}}; {{harvtxt|Skodinis|2000}}; {{harvtxt|Skodinis|2003}}; {{harvtxt|Coudert|Huc|Mazauric|2012}}.</ref>对树宽有界图族（[[系列并行图]]、[[外平面图]]、[[哈林图]]）<ref name="bounded-tw-algs">{{harvtxt|Bodlaender|1996}}; {{harvtxt|Bodlaender|Kloks|1996}}</ref>、[[裂图]]<ref>{{harvtxt|Kloks|Bodlaender|1992}}; {{harvtxt|Gustedt|1993}}.</ref>、弦图之补<ref>{{harvtxt|Garbe|1995}}将此成果归功于Ton Kloks的博士论文（1993）；Garbe对区间序的可比图的多项式时间算法推广了结果，而弦图属于此类可比图。</ref>、[[置换图]]<ref name="bkk93"/>、[[余图]]<ref name="bm90"/>、[[圆弧图]]<ref>{{harvtxt|Suchan|Todinca|2007}}.</ref>、区间序的可比图<ref name="g95"/>、[[区间图]]，也可在多项式时间内计算出来。这种情形下，径宽比覆盖图的区间表示中所有点的最大区间数小1。

@@ 第39行： / 第39行： @@
 ==界==
-[[File:Caterpillar tree.svg|thumb|[[毛虫树]]，径宽为1的最大图。]]
+[[文件:Caterpillar tree.svg|thumb|[[毛虫树]]，径宽为1的最大图。]]
 径宽为''k''的''n''顶点图至多有<math>k(n-k+\frac{k-1}{2})</math>条边，是最大''k''径宽图（即径宽为''k''、无论怎样添加边都必改变径宽的图）的边数。径宽为''k''的最大图要么是''k''径图要么是''k''毛虫图，它们是两种特殊的''k''树。''k''树是恰有<math>n-k</math>个[[最大团]]（含<math>k+1</math>个顶点）的[[弦图]]；在本身不是<math>(k+1)</math>团的''k''树中，每个最大团要么将图分隔成多个部分，要么包含单个叶顶点（只属于一个最大团的顶点）。''k''径图是至少有两叶的''k''树，''k''毛虫图是可分割维''k''径与一组''k''叶的''k''树，其中每片叶还与''k''径中的独立''k''团相邻。径宽为1的最大图是[[毛虫树]]。<ref>{{harvtxt|Proskurowski|Telle|1999}}.</ref>
@@ 第52行： / 第52行： @@
 在某些类的图中，径宽与树宽总相等。已证明的有[[余图]]、<ref name="bm90">{{harvtxt|Bodlaender|Möhring|1990}}.</ref>[[置换图]]、<ref name="bkk93">{{harvtxt|Bodlaender|Kloks|Kratsch|1993}}.</ref>[[可比图]]之[[补图|补]]、<ref name="hm94">{{harvtxt|Habib|Möhring|1994}}.</ref>[[区间序]]的可比图。<ref name="g95">{{harvtxt|Garbe|1995}}.</ref>
 在[[立方图]]中，或更广义地在任何最大顶点度为3的图中，径宽不大于<math>\frac{n}{6}+o(n)</math>，其中''n''是顶点数。存在径宽为<math>0.082n</math>的立方图，但如何缩小这下界与上界<math>\frac{n}{6}</math>之间的差距，目前还不得而知。<ref name="fh06">{{harvtxt|Fomin|Høie|2006}}.</ref>

@@ 第22行： / 第22行： @@
 ===区间厚度===
-[[File:Interval graph.svg|thumb|upright=1.25|径宽为2的[[区间图]]，而4个最大团ABC、ACD、CDE、CDF的大小为3。]]
+[[文件:Interval graph.svg|thumb|upright=1.25|径宽为2的[[区间图]]，而4个最大团ABC、ACD、CDE、CDF的大小为3。]]
 任意图''G''的径宽等于含''G''（以''G''为子图）的[[区间图]]的最小团数减一。<ref>{{harvtxt|Bodlaender|1998}}, Theorem 29, p. 13.</ref>即，对''G''的每种径分解，都能找到''G''的区间子图；对''G''的每个区间父图，都能找到''G''的径分解，使分解的宽度比区间图团数小1。

@@ 第8行： / 第8行： @@
 ==定义==
-[[文件:Pathwidth.jpg|thumb|upright=1.35|径宽为2的例图''G''，其径分解宽度为2。图像下半部是相同的图与径分解，添加了颜色以示强调。（本例改编自{{harvp|Bodlaender|1994a}}，添加了记号）]]
+[[文件:Pathwidth.jpg|thumb|upright=1.35|径宽为2的例图''G''，其径分解宽度为2。图像下半部是相同的图与径分解，添加了颜色以示强调。]]
 Neil Robertson and Paul Seymour （1983）在[[图子式]]系列论文的第一篇中，将图''G''的径分解定义为''G''的顶点子集<math>X_i</math>序列，满足两条属性：
 # 对''G''中每条边，存在''i''使边的两端点都属于子集<math>X_i</math>；

←上一版本		2025年6月21日 (六) 09:06的版本
第114行：		第114行：

	同样的动态规划方法也可用于径宽无界图，产生以[[时间复杂度#指数时间\|指数时间]]解决无参图问题的算法。例如，将这种方法与[[立方图]]径宽为<math>\frac{n}{6}+o(n)</math>的事实相结合，可以发现在立方图中，最大[[支配集]]的构造耗时<math>O(2^{\frac{n}{6}+o(n)})</math>，比以往方法更快。<ref name="fh06"/>类似方法还可改进立方图中[[最大割]]与最小支配集问题的指数时间算法，<ref name="fh06"/>及其他一些NP难优化问题的指数时间算法。<ref>{{harvtxt\|Kneis\|Mölle\|Richter\|Rossmanith\|2005}}; {{harvtxt\|Björklund\|Husfeldt\|2008}}.</ref>		同样的动态规划方法也可用于径宽无界图，产生以[[时间复杂度#指数时间\|指数时间]]解决无参图问题的算法。例如，将这种方法与[[立方图]]径宽为<math>\frac{n}{6}+o(n)</math>的事实相结合，可以发现在立方图中，最大[[支配集]]的构造耗时<math>O(2^{\frac{n}{6}+o(n)})</math>，比以往方法更快。<ref name="fh06"/>类似方法还可改进立方图中[[最大割]]与最小支配集问题的指数时间算法，<ref name="fh06"/>及其他一些NP难优化问题的指数时间算法。<ref>{{harvtxt\|Kneis\|Mölle\|Richter\|Rossmanith\|2005}}; {{harvtxt\|Björklund\|Husfeldt\|2008}}.</ref>
		+

	==注释==		==注释==

←上一版本		2025年6月21日 (六) 09:05的版本
第114行：		第114行：

	同样的动态规划方法也可用于径宽无界图，产生以[[时间复杂度#指数时间\|指数时间]]解决无参图问题的算法。例如，将这种方法与[[立方图]]径宽为<math>\frac{n}{6}+o(n)</math>的事实相结合，可以发现在立方图中，最大[[支配集]]的构造耗时<math>O(2^{\frac{n}{6}+o(n)})</math>，比以往方法更快。<ref name="fh06"/>类似方法还可改进立方图中[[最大割]]与最小支配集问题的指数时间算法，<ref name="fh06"/>及其他一些NP难优化问题的指数时间算法。<ref>{{harvtxt\|Kneis\|Mölle\|Richter\|Rossmanith\|2005}}; {{harvtxt\|Björklund\|Husfeldt\|2008}}.</ref>		同样的动态规划方法也可用于径宽无界图，产生以[[时间复杂度#指数时间\|指数时间]]解决无参图问题的算法。例如，将这种方法与[[立方图]]径宽为<math>\frac{n}{6}+o(n)</math>的事实相结合，可以发现在立方图中，最大[[支配集]]的构造耗时<math>O(2^{\frac{n}{6}+o(n)})</math>，比以往方法更快。<ref name="fh06"/>类似方法还可改进立方图中[[最大割]]与最小支配集问题的指数时间算法，<ref name="fh06"/>及其他一些NP难优化问题的指数时间算法。<ref>{{harvtxt\|Kneis\|Mölle\|Richter\|Rossmanith\|2005}}; {{harvtxt\|Björklund\|Husfeldt\|2008}}.</ref>
		+
		+	==另见==
		+	*[[箱性]]
		+	*[[割宽]]
		+	*[[树深]]
		+	*[[退化 (图论)]]
		+	*[[带宽 (图论)]]
		+
		+	*[[斯特拉勒数]]

	==注释==		==注释==