学位论文 > 优秀研究生学位论文题录展示

图的交叉数问题研究

作　者: 郑文萍
导　师: 杨元生
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 交叉数 交图 正则图 路径幂图 圈 路径 完全图 完全二部图 轮图 双锥图 Kn(o ¨)del图 Flower Snark
分类号: TP391.72
类　型: 博士论文
年　份: 2007年
下　载: 114次
引　用: 3次
阅　读: 论文下载
 

内容摘要


图的交叉数问题是在实际应用中提出来的，在电子线路板的设计，CAD领域有广阔的应用。目前已经确定交叉数的图类主要集中于顶点数较小或者交叉数较小的图。本文对一些顶点数较大或交叉数较大的图的交叉数问题进行研究，将计算机构造性证明和数学证明相结合，取得了较好的结果。本课题组给出的交叉数算法CCN已被成功地用于计算顶点数较小的图的交叉数。但由于图的交叉数问题是NP困难问题，对顶点数较大或交叉数较大的图，所需要的计算时间仍然太多。针对这一问题，本文给出了计算图的交叉数上界的算法CCN*，把计算图的交叉数上界问题转化为计算往其子图的较少交叉点画法中回添边时所产生的交叉数的问题，从而可以对较大规模的图的交叉数性质进行研究。利用该算法计算了顶点数p≤12的所有路径幂图Pnk和13≤p≤20且k≤9的所有Pnk的较好的交叉数上界。对与圈Cn交图的交叉数，目前研究的较多的是两个圈的交图以及顶点数较小的图与圈交图的交叉数。Ringeisen和Beineke对Km□Cn，m≤4进行了研究。本文对Km□Cn进行研究，给出了相应的交叉数计数方法，确定了这类图的交叉数下界。对m=5，6，7或者n为不小于4的偶数，给出了交叉数上界及对应的画法；如果著名的完全图交叉数猜想对Km+2成立，则本文给出的交叉数上界就是完全图Km与圈Cn交图的交叉数。对与路径Pn交图的交叉数，目前研究的较多的也是顶点数较小的图与路径交图的交叉数。Kle（?）等人对Km□Pn，m≤5进行了研究。Bokal对K1，l□Pn进行了研究。黄元秋与Kle（?）分别研究了Wm□Pn的n≤3与m=3，4的情形；Kle（?）对W2，3□Pn进行了研究。本文针对Km□Pn，Km，l□Pn，Wl，m□Pn进行了研究，给出了这些图的交叉数上界。并对其中Km□Pn，K2，l□Pn，Wm□Pn，W2，m□Pn给出了相应的交叉数计数方法，进而导出了这些图的交叉数下界。并最终确定了K6□Pn，K2，l□Pn，Wm□Pn，W2，m□Pn的交叉数，扩展了与路径交图的交叉数的研究结果。本文所给出的交叉数研究方法还可以用于研究其它图的交叉数问题。作为应用实例，本文确定了两类三正则图Kn（?）del图J3，n和Flower Snark及其相关图Fn的交叉数。相信该方法在图的交叉数问题研究中还有更广泛的应用。

全文目录


摘要  4-5
Abstract  5-6
目录  6-8
1 绪论  8-21
  1.1 一些符号及预备知识  8-14
  1.2 交叉数问题的研究现状  14-19
    1.2.1 完全图的交叉数  15-16
    1.2.2 完全二部图的交叉数  16
    1.2.3 完全三部图的交叉数  16-17
    1.2.4 广义Petersen图和循环图的交叉数  17
    1.2.5 交图的交叉数  17-19
    1.2.6 其它研究进展  19
  1.3 本文工作  19-21
2 路径幂图P_n~k的交叉数  21-41
  2.1 计算图的交叉数上界的算法  21-23
  2.2 路径幂图P_n~k(k=1,2,3,4,5,n-1,n)的交叉数  23-28
  2.3 P_n~k的交叉数上界  28-35
  2.4 小结与猜想  35-41
3 完全图与圈交图的交叉数  41-56
  3.1 K_m□C_n的交叉数下界  41-49
  3.2 K_m□C_n(n为偶数)的交叉数  49-53
  3.3 K_5□C_n,K_6□C_n,K_7□C_n的交叉数  53-55
  3.4 小结与猜想  55-56
4 完全图与路径交图的交叉数  56-65
  4.1 K_m□P_n的交叉数下界  56-58
  4.2 K_m□P_n的交叉数上界  58-61
  4.3 K_6□P_n的交叉数  61-63
  4.4 小结与猜想  63-65
5 完全二部图、多锥图与路径交图的交叉数  65-82
  5.1 完全二部图与路径交图的交叉数  65-70
    5.1.1 cr(K_(m,l)□P_n)(n≥1且min{m,l}≥2)的上界  65-68
    5.1.2 K_(2,l)□P_n的交叉数  68-70
  5.2 多锥图W_(l,m)=C_m+(?)与路径交图的交叉数  70-80
    5.2.1 基本引理  70-72
    5.2.2 轮图W_m与路径交图的交叉数  72-75
    5.2.3 锥图W_(2,m)与路径交图的交叉数  75-79
    5.2.4 多锥图与路径交图的交叉数上界  79-80
  5.3 小结与猜想  80-82
6 两类三正则图的交叉数  82-99
  6.1 Knodel图J_(3,n)的交叉数  82-93
  6.2 Flower Snark及其相关图的交叉数  93-99
7 总结与展望  99-102
创新点摘要  102-103
参考文献  103-112
攻读博士学位期间参加的科研项目和发表的学术论文  112-113
致谢  113-114

相似论文

  1. Flower Snark图与Kn(?)del图的亲切素标号,O157.5
  2. 若干图的等全着色及彩虹支配问题的研究,O157.5
  3. W_（3，n）和K_m□C_n的交叉数,TP301
  4. 完全二部图K_（n，n）的循环圈分解及边—平衡指数集,O157.5
  5. 厌氧颗粒污泥对活性黑KN-B染料的生物降解脱色研究,X703
  6. 超可解构形与二次构形的关系及其相关问题,O157.5
  7. 关于图的自同态的研究,O157.5
  8. 局部2-弧传递的完全二部图,O157.5
  9. 关于k阶限制边连通度若干问题的研究,O157.5
  10. 图的泛宽度染色和（p，1）—全标号,O157.5
  11. 关于图的交叉数问题研究,O157.5
  12. 循环图的交叉数,O157.5
  13. 五阶图与星图的笛卡尔积图的交叉数,O157.5
  14. 五阶图与星图的笛卡尔积的交叉数,O157.5
  15. 路径与完全图，完全二分图的交图的交叉数,TP301
  16. 几类冠图的临界群,O157.5
  17. HW（r，s；h，8）存在性问题的研究,O157.5
  18. 完全图的{3，4，8}-圈分解,O157.5
  19. 完全图的{3，6，8}-圈分解,O157.5
  20. 关于平面直线构形的φ_3不变量,O185

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 信息处理（信息加工） > 机器辅助技术 > 机器辅助设计（CAD）、辅助制图
© 2012 www.xueweilunwen.com