一、三正则图及其相关图的交叉数问题（论文文献综述）
张思佳[1]（2016）在《几类重要互连网络拓扑结构图的反馈数研究》文中研究表明图的反馈数问题是在实际应用中提出来的。计算机操作系统中解决“死锁”问题、网络攻击中最小攻击点集问题等都可以转化为在图中求一个最小反馈点集的问题。求图的反馈数问题已被证明是NP困难问题,其每一个进展都十分艰辛。到目前为止,只有少数的图类得到了其反馈数,已经得到反馈数界的图类也不多。本文对与互连网络拓扑结构设计方法（笛卡儿乘积方法、线图方法、Cayley方法）密切相关的几个重要的图类的反馈数进行了研究,分别给出了Flower Snark相关图Jn、Knodel图W△,n。和循环图Gn（1,k）的反馈数、增广立方体AQn反馈数的上下界、局部扭立方体LTQn反馈数的上界以及Kautz有向图K（d,n）反馈数的上界。（1）对Flower Snark相关图Jn、Knodel图W3,n和W4,n、循环图Cn（1,K）的反馈数进行了研究。利用Jn、W3,n、W4,n和Gn（1,k）的循环结构,分别找到了相应的带循环节的无圈子图顶点集的构造方法,基于这些顶点集分别得到了如下结论。①给出了Flower Snark相关图Jn反馈数为：f（Jn）=n+1；②给出了W3,n反馈数：f（W3,n）=（?）；③给出了W4,n反馈数：f（W4,n）=（?）；④ 给出了偶数n≥5+1+2（?）+mod3)且3≤奇数k<n/2时的Cn（1,k）反馈数：f（Cn（1,k））=（?）（2） 对增广立方体AQn、局部扭立方体LTQn两种变型超立方体网络的反馈数进行了研究。利用AQn和LTQn顶点递推结构和边集性质,分别构造出了相应的可递推的无圈子图顶点集函数,基于这些函数,分别给出如下结论。①给出了AQn反馈数紧的上下界为：2n-3×2n-3≤f（AQ）≤2n-（2n-2+2（?））；②给出了LTQn反馈数的上界为：f（LTQn）≤2n-1。（3）对有向Kautz图K（d,n）的反馈数进行了研究。给出了Kautz有向图K（d,n）的一种新的反馈点集顶点短表达式模式,基于该模式得到了更小的反馈点集,给出K（d,n）渐进估计从O（dn-4）下降到O（d2）。
杨希武[2]（2008）在《Flower Snark和Km-e□Pn的交叉数》文中研究表明图的交叉数是衡量图的非平面性的一个重要参数，计算图的交叉数是非常困难的，Garey和Johnson在1983年证明了计算图的交叉数问题是NP完全的。目前只有很少的图的交叉数的精确值是已知的，比如广义Petersen图P（n，3），所有5个顶点的图与路径的交图等，而完全图、完全二分图等图族的交叉数仍然是拓扑图论中待解决的难题。本文对三正则图Flower Snark及其相关图Fn（n≥3）和Twisted Flower Snark及其相关图Fn*（n≥3）的交叉数进行了研究，分别给出了这两类图的交叉数的精确值。证明了cr（F3）=2、cr（F4）=3、cr（F5）=4、cr（Fn）=n（n≥6）。cr（F3*）=1、cr（F4*）=2、cr（F5*）=4、cr（Fn*）=n（n≥6）。另外本文还研究了路径与图Km-e的交图Km-e□Pn的交叉数。首先给出了这类图的交叉数上界：同时给出了Km-e□Pn的交叉数下界公式：进一步本文确定了K6-e□Pn的交叉数：cr（K6-e□Pn）=12n，n≥1。
郑文萍[3]（2007）在《图的交叉数问题研究》文中研究表明图的交叉数问题是在实际应用中提出来的，在电子线路板的设计，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]（2002）在《三正则图及其相关图的交叉数问题》文中认为利用计算交叉数的算法CCN（Calculate Crossing Number），本文对三正则图的交叉数与围长的关系进行了深入的研究。通过研究n≤15的所有三正则的广义Petersen图P（n，k），n≤18的所有三正则图，20≤n≤30的随机三正则图与具有最大围长的三正则图，n≤18的所有循环图Cn（1，k），本文得到如下规律：对于给定的顶点数n（n≤18），具有最大围长的三正则图的平均交叉数大于所有三正则图的平均交叉数。本文还给出了循环图Cn（1，k）和广义Petersen图P（n，k）的交叉数关系。
二、三正则图及其相关图的交叉数问题（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、三正则图及其相关图的交叉数问题（论文提纲范文）
（1）几类重要互连网络拓扑结构图的反馈数研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 主要符号表 |
| 1 绪论 |
| 1.1 互连网络拓扑结构设计的基本方法 |
| 1.2 反馈数问题的研究现状 |
| 1.3 一些符号及预备知识 |
| 1.4 本文主要工作 |
| 2 Flower Snark相关图及几类亚循环图的反馈数 |
| 2.1 Flower Snark相关图的反馈数 |
| 2.1.1 Flower Snark相关图无圈点集的构造 |
| 2.1.2 Flower Snark相关图的反馈数 |
| 2.2 W_(3,n)图的反馈数 |
| 2.2.1 nmod4=0时W_(3,n)无圈点集的构造 |
| 2.2.2 nmod4=2时W_(3,n)无圈点集的构造 |
| 2.2.3 W_(3,n)的反馈数 |
| 2.3 W_(4,n)图的反馈数 |
| 2.3.1 n=20,32,38和56无圈点集的构造 |
| 2.3.2 W_(4,n)图无圈点集的构造 |
| 2.3.3 W_(3,n)的反馈数 |
| 2.4 循环图C_n(1,k)的反馈数 |
| 2.4.1 循环图C_n(1,k)无圈点集的构造 |
| 2.4.2 循环图C_n(1,k)的反馈数 |
| 2.5 本章小结 |
| 3 变型超立方体网络结构图的反馈数 |
| 3.1 增广立方体AQ_n的反馈数 |
| 3.1.1 增广立方体AQ_n无圈点集的构造 |
| 3.1.2 增广立方体AQ_n的反馈数 |
| 3.2 局部扭立方体LTQ_n的反馈数 |
| 3.2.1 局部扭立方体LTQ_n无圈点集的构造 |
| 3.2.2 局部扭立方体LTQ_n的反馈数 |
| 3.3 本章小结 |
| 4 Kautz图K(d,n)的反馈数 |
| 4.1 K(d,n)反馈数的研究基础 |
| 4.2 K(d,n)反馈点集的构造 |
| 4.3 K(d,n)的反馈数 |
| 4.4 本章小结 |
| 5 结论与展望 |
| 5.1 结论 |
| 5.2 创新点 |
| 5.3 展望 |
| 参考文献 |
| 攻读博士学位期间科研项目及科研成果 |
| 致谢 |
| 作者简介 |
（2）Flower Snark和Km-e□Pn的交叉数（论文提纲范文）
| 摘要 |
| Abstract |
| 1 绪论 |
| 1.1 图的交叉数的研究意义 |
| 1.2 图及交叉数的基本概念 |
| 1.3 图的交叉数的研究进展 |
| 1.3.1 完全图 |
| 1.3.2 完全二分图 |
| 1.3.3 完全三分图 |
| 1.3.4 交图 |
| 1.4 本文的主要工作 |
| 2 计算图的交叉数——算法CCN |
| 2.1 画法的计算机表示方法 |
| 2.2 计算图的交叉数的相关算法 |
| 2.3 用算法CCN计算给定图的交叉数 |
| 3 Flower Snark的交叉数 |
| 3.1 Flower Snark图 |
| 3.2 F_n的交叉数 |
| 3.2.1 图F_n的交叉数的上界 |
| 3.2.2 图F_n的交叉数的下界 |
| 3.3 F_n~*的交叉数 |
| 3.3.1 图F_n~*的交叉数的上界 |
| 3.3.2 图F_n~*的交叉数的下界 |
| 4 路径与图K_m-e交图的交叉数 |
| 4.1 cr(K_m-e□P_n)的上界 |
| 4.2 cr(K_m-e□P_n)的下界 |
| 4.3 cr(K_6-e□P_n)=12n |
| 结论 |
| 参考文献 |
| 攻读硕士学位期间发表学术论文情况 |
| 致谢 |
（3）图的交叉数问题研究（论文提纲范文）
| 摘要 |
| Abstract |
| 目录 |
| 1 绪论 |
| 1.1 一些符号及预备知识 |
| 1.2 交叉数问题的研究现状 |
| 1.2.1 完全图的交叉数 |
| 1.2.2 完全二部图的交叉数 |
| 1.2.3 完全三部图的交叉数 |
| 1.2.4 广义Petersen图和循环图的交叉数 |
| 1.2.5 交图的交叉数 |
| 1.2.6 其它研究进展 |
| 1.3 本文工作 |
| 2 路径幂图P_n~k的交叉数 |
| 2.1 计算图的交叉数上界的算法 |
| 2.2 路径幂图P_n~k(k=1,2,3,4,5,n-1,n)的交叉数 |
| 2.3 P_n~k的交叉数上界 |
| 2.4 小结与猜想 |
| 3 完全图与圈交图的交叉数 |
| 3.1 K_m□C_n的交叉数下界 |
| 3.2 K_m□C_n(n为偶数)的交叉数 |
| 3.3 K_5□C_n,K_6□C_n,K_7□C_n的交叉数 |
| 3.4 小结与猜想 |
| 4 完全图与路径交图的交叉数 |
| 4.1 K_m□P_n的交叉数下界 |
| 4.2 K_m□P_n的交叉数上界 |
| 4.3 K_6□P_n的交叉数 |
| 4.4 小结与猜想 |
| 5 完全二部图、多锥图与路径交图的交叉数 |
| 5.1 完全二部图与路径交图的交叉数 |
| 5.1.1 cr(K_(m,l)□P_n)(n≥1且min{m,l}≥2)的上界 |
| 5.1.2 K_(2,l)□P_n的交叉数 |
| 5.2 多锥图W_(l,m)=C_m+(?)与路径交图的交叉数 |
| 5.2.1 基本引理 |
| 5.2.2 轮图W_m与路径交图的交叉数 |
| 5.2.3 锥图W_(2,m)与路径交图的交叉数 |
| 5.2.4 多锥图与路径交图的交叉数上界 |
| 5.3 小结与猜想 |
| 6 两类三正则图的交叉数 |
| 6.1 Knodel图J_(3,n)的交叉数 |
| 6.2 Flower Snark及其相关图的交叉数 |
| 7 总结与展望 |
| 创新点摘要 |
| 参考文献 |
| 攻读博士学位期间参加的科研项目和发表的学术论文 |
| 致谢 |
（4）三正则图及其相关图的交叉数问题（论文提纲范文）
| 1 引言 |
| 1.1 基本概念 |
| 1.2 交叉数问题的研究现状 |
| 1.2.1 完全图K_n |
| 1.2.2 完全二分图K_（m,n） |
| 1.2.3 完全三分图K_（1,m,n） |
| 1.2.4 交图C_m×C_n |
| 1.2.5 广义Petersen图P（n，k） |
| 1.2.6 N方图Q_n |
| 1.2.7 正则图 |
| 1.3 本文研究结果 |
| 2 CCN算法描述与实例分析 |
| 2.1 CCN算法设计思想 |
| 2.2 CCN算法描述 |
| 2.3 CCN算法的实例分析 |
| 3 三正则图的交叉数与围长 |
| 3.1 n≤18的所有连通的三正则图的交叉数 |
| 3.2 20≤n≤30随机三正则图的交叉数 |
| 3.3 n≤30的所有具有最大围长的三正则图的平均交叉数 |
| 3.4 结果与分析 |
| 4 与三正则图相关的图的交叉数问题 |
| 4.1 广义Petersen图 |
| 4.1.1 广义Petersen图的特点 |
| 4.1.2 n≤15的三正则广义Petersen图的交叉数与围长 |
| 4.1.3 结果与分析 |
| 4.2 循环图C_n（1，k） |
| 4.2.1 循环图C_n（1，k）的特点 |
| 4.2.2 循环图C_n（1，k）的同构定理 |
| 4.2.3 循环图C_n（1，k）的交叉数 |
| 4.2.4 循环图C_n（1，k）的一些特殊图的交叉数 |
| 4.2.5 循环图C_n（1，k）与广义Petersen图的交叉数关系 |
| 5 小结 |
| 参考文献 |
| 致谢 |
四、三正则图及其相关图的交叉数问题（论文参考文献）
- [1]几类重要互连网络拓扑结构图的反馈数研究[D]. 张思佳. 大连理工大学, 2016(03)
- [2]Flower Snark和Km-e□Pn的交叉数[D]. 杨希武. 大连理工大学, 2008(05)
- [3]图的交叉数问题研究[D]. 郑文萍. 大连理工大学, 2007(02)
- [4]三正则图及其相关图的交叉数问题[D]. 赵承业. 大连理工大学, 2002(02)
标签：完全图论文;