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

不超过9个顶点的所有图的交叉数

作　者: 孙艳春
导　师: 杨元生；陈连玉
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 交叉数 正则图 围长
分类号: O157.5
类　型: 硕士论文
年　份: 2002年
下　载: 30次
引　用: 0次
阅　读: 论文下载
 

内容摘要


利用我们研制的计算图的交叉数的算法CCN(Calculate Crossing Number)，本文对n≤9的所有图的交叉数进行了研究。由于图的交叉数等于其所有二连通分支的交叉数的和，本文计算了n≤9的所有单二连通分支图的交叉数。并得出相关的规律：1)n个顶点q条边的单二连通分支图的平均交叉数Aac(n,q)可近似地表示为q的二次多项式，2)在给定顶点数n与边数q的单二连通分支图中围长较大的图的平均交叉数大于围长较小的图的平均交叉数，3)在给定顶点数n与边数q的单二连通分支图中当n为奇数或r≤n/2时，r正则图的平均交叉数大于非r正则图的平均交叉数。还证明了Erdos和Guy关于可能有最大的交叉数的图的猜想不成立。

全文目录


1 图论基本知识  6-10
2 图的交叉数问题的进展  10-22
  2．1 图论简史  10-11
  2．2 图的交叉数问题的研究现状  11-21
    2．2．1 完全图的交叉数  11-14
    2．2．2 完全二分图的交叉数  14-15
    2．2．3 完全三分图的交叉数  15
    2．2．4 n方图的交叉数  15-16
    2．2．5 交图的交叉数  16
    2．2．6 广义Petersen图的交叉数  16-18
    2．2．7 正则图的交叉数  18
    2．2．8 一般图的交叉数  18-19
    2．2．9 三正则图的围长对其交叉数的影响  19-21
  2．3 本文研究结果  21-22
3 计算机实现  22-35
  3．1 概述  22
  3．2 利用算法CCN求单二连通分支图G的交叉数  22-25
  3．3 6≤n≤9且n+3≤q的所有单二连通分支图的交叉数  25-32
  3．4 图的围长与其交叉数的关系  32-33
  3．5 正则图平均交叉数与非正则图平均交叉数的关系  33-35
4 小结  35-36
参考文献  36-38
致谢  38

相似论文

  1. 多进制LDPC码构造方法的研究,TN911.22
  2. M(?)bius cubes图的交叉数,O157.5
  3. 局部扭立方体图的交叉数研究,O157.5
  4. 一类4p~2阶群的小度数Cayley图,O157.5
  5. 基于围长搜索的LDPC码构造算法研究,TN911.2
  6. 一种改进PS-LDPC码的研究及FPGA设计,TN791
  7. 直接乘积图的超级3限制边连通性,O157.5
  8. 双圈图的特征值与结构参数,O157.5
  9. 二面体群上的群环的零因子图,O153.3
  10. 三次对称群上的群环的零因子图,O153.3
  11. 平面图的边列表染色和线性染色,O157.5
  12. 图的临界群和染色唯一性的研究,O157.5
  13. 给定围长的图的超三限制性连通度的充分条件,O157.5
  14. R（+）M与R（？）I的零因子图,O153.3
  15. Z_n[ω]与形式三角矩阵环的零因子图,O153.3
  16. 群环的零因子图,O153.3
  17. 两类图的一些极值问题研究,O157.5
  18. 关于图的笛卡尔积交叉数的研究,O157.5
  19. 低密度校验码的围长提升研究,TN911.2
  20. 图的线性染色,O157.5
  21. 非规则LDPC码的局部消环技术及其相关技术的研究,TN911.2

中图分类: > 数理科学和化学 > 数学 > 代数、数论、组合理论 > 组合数学（组合学） > 图论
© 2012 www.xueweilunwen.com