91
个编辑
更改
跳到导航
跳到搜索
第39行：
第39行： − + 第52行：
第52行： − {{unsolved|数学|''n''顶点[[立方图]]的径宽上界是多少？}}
→界
==界==
==界==
[[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>
径宽为''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>
在某些类的图中，径宽与树宽总相等。已证明的有[[余图]]、<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>
在某些类的图中，径宽与树宽总相等。已证明的有[[余图]]、<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>
在[[立方图]]中，或更广义地在任何最大顶点度为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>