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

W_（3，n）和K_m□C_n的交叉数

作　者: 邓成瑞
导　师: 杨元生
学　校: 大连理工大学
专　业: 计算机软件与理论
关键词: 交叉数 Kn(o ¨)del图交图
分类号: TP301
类　型: 硕士论文
年　份: 2006年
下　载: 16次
引　用: 0次
阅　读: 论文下载

内容摘要

图的交叉数是衡量图的非平面性的一个重要参数，Garey和Johnson证明了计算图的交叉数问题是NP完全的。目前仅确定了少数几类图的交叉数。完全图，完全二分图，广义Petersen图，循环图，顶点数较小的图与路径、圈或者星图的交图是交叉数问题中活跃的研究对象。 Kn（?）del图是一种互连网络，研究互连网络的交叉数有助于更好地理解其拓扑性质。本文研究了Kn（?）del图W_3，n（n≥8，n为偶数）的交叉数。首先利用计算机构造了W_3，n交叉数较少的画法，给出交叉数上界；然后设计了W_3，n的边分组方式和交叉点计数函数给出其下界。最终证明： cr(W_3，8)=0；cr(W_3，10)=1；cr(W_3，n)=[n/6]+n mod 6/2，当n≥12时。 Ringeisen和Beineke给出了K₃□C_n以及K₄□C_n的交叉数。本文进一步研究了完全图和圈的交图K_m□C_n的交叉数。通过设计K_m□C_n的分组方式和交叉点计数方法，给出了K_m□C_n交叉数的下界： cr（K_m□C_n）≥n cr(K_m+2)。通过改进计算图的交叉数算法CCN的限界条件，利用计算机构造了K_m□C_n好的画法，给出了K_m□C_n交叉数的上界： cr（K_m□C_n）≤n/4[m+2/2][m+1/2][2/2][m-1/2]（n为偶数）； cr（K_m□C_n）≤n/4[m+2/2][m+1/2][m/2][m-1/2]+[m-1/2]²（n为奇数）。因为m≤12时Guy给出的完全图交叉数猜想成立，所以当m≤10，n为偶数时，有： cr（K_m□C_n）=n/4[m+2/2][m+1/2][m/2][m-1/2]（m≤10且n为偶数）。当n为奇数时，利用计算机构造出了K₅□C_n，K₆□C_n和K₇口C_n的交叉数更少的画法，进一步改进了上界。从而完全确定了这三类图的交叉数： cr（K₅□C_n）=9n；cr（K₆□C_n）=18n；cr（K₇□C_n）=36n。

全文目录

摘要  3-5
Abstract  5-9
1 绪论  9-20
  1.1 图及交叉数基本概念  9-13
  1.2 交叉数领域的研究状况  13-19
    1.2.1 完全图的交叉数  13
    1.2.2 完全二分图的交叉数  13-14
    1.2.3 完全三分图的交叉数  14
    1.2.4 交图的交叉数  14-16
    1.2.5 广义Petersen图的交叉数  16-17
    1.2.6 循环图的交叉数  17-19
    1.2.7 N方图Q_n的交叉数  19
    1.2.8 分形图的交叉数  19
  1.3 本文工作  19-20
2 计算图的交叉数——算法CCN  20-26
  2.1 画法的计算机表示方法  21-22
  2.2 计算图的交叉数的相关算法  22-25
    2.2.1 图的平面性判定算法  22-23
    2.2.2 计算图的交叉数算法CCN  23-25
  2.3 计算给定图的交叉数  25-26
    2.3.1 对于小阶Kn(o|¨)del图W_(3,n)的计算结果  25
    2.3.2 对于图K_m□C_n的计算结果  25-26
3 Kn(o|¨)del图W_3,n的交叉数  26-40
  3.1 Kn(o|¨)del图  26-27
    3.1.1 Kn(o|¨)del图的定义  26
    3.1.2 Kn(o|¨)del图的应用与交叉数  26-27
  3.2 基本引理  27-28
  3.3 Kn(o|¨)del图W_(3,n)的交叉数的上界  28-29
  3.4 Kn(o|¨)del图W_(3,n)的交叉数的下界  29-39
  3.5 Kn(o|¨)del图W_(3,n)的交叉数  39
  3.6 Kn(o|¨)del图W_(4,n)的交叉数  39-40
4 交图K_m□C_n的交叉数  40-56
  4.1 交图K_m□C_n  40
  4.2 交图K_m□C_n的交叉数下界  40-46
  4.3 交图K_m□C_n的交叉数  46-52
  4.4 K_5□C_n,K_6□C_n,K_7□C_n的交叉数  52-53
  4.5 猜想  53-56
结论  56-58
参考文献  58-61
攻读硕士学位期间发表学术论文情况  61-62
致谢  62-63

相似论文

组合SBR法处理含活性艳兰KN-G印染废水的研究,X703
完全二部图K_（n，n）的循环圈分解及边—平衡指数集,O157.5
联图与笛卡尔积图类的交叉数研究,O157.5
图的泛宽度染色和（p，1）—全标号,O157.5
W_（3，n）的支配问题与二部图的弧的公有性研究,O157.5
几何图论中的若干问题,O157.5
匹配与对合中的有禁模式,O157.5
KN-93和顺铂通过c-FLIP表达的下调和磷酸化抑制恶性肿瘤Fas介导细胞凋亡的耐受,R730.5
2+1维可积方程的有限亏格解,O175
图的交叉数问题研究,TP391.72
关于图的交叉数研究,O157.5
MW/UV/TiO_2方法处理典型活性染料废水研究,X791
关于一些特殊图类的交叉数研究,O157.5
图的交叉数等图论难题的研究,O157.5
关于循环图及一些特殊图与路、星、树和圈的笛卡尔积的交叉数研究,O157.5
若干图类交叉数的研究,O157.5
纽结补中的不可压缩边界不可压缩曲面的性质,O189.24
笛卡儿积图交叉数的若干结果,O157.5
不超过9个顶点的所有图的交叉数,O157.5
三正则图及其相关图的交叉数问题,O157.5