91
个编辑
更改
→径宽有界的障碍
从一个方向来看，这结果很容易证明：若''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>
从一个方向来看，这结果很容易证明：若''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>
径宽不大于''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>