91
个编辑
更改
跳到导航
跳到搜索
第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。
任意图''G''的径宽等于含''G''（以''G''为子图）的[[区间图]]的最小团数减一。<ref>{{harvtxt|Bodlaender|1998}}, Theorem 29, p. 13.</ref>即，对''G''的每种径分解，都能找到''G''的区间子图；对''G''的每个区间父图，都能找到''G''的径分解，使分解的宽度比区间图团数小1。