91
个编辑
更改
跳到导航
跳到搜索
第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>序列，满足两条属性：
Neil Robertson and Paul Seymour （1983）在[[图子式]]系列论文的第一篇中，将图''G''的径分解定义为''G''的顶点子集<math>X_i</math>序列，满足两条属性：
# 对''G''中每条边，存在''i''使边的两端点都属于子集<math>X_i</math>；
# 对''G''中每条边，存在''i''使边的两端点都属于子集<math>X_i</math>；