关于图的交叉数的研究

来源 :湖南师范大学 | 被引量 : 0次 | 上传用户:soton0001
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的交叉数是图论中的一个重要概念,目前图的交叉数问题已成为国际上一个非常活跃的图论分支.研究图的交叉数不仅具有重要的理论意义,而且具有特有的实践意义,在许多领域有着非常广泛的作用,如工业上电子线路板设计中的布线问题;生物工程DNA的图示;软件开发过程中文档部分的ER图(实体联系图)等的自动生成等等. 已经知道确定图的交叉数是一个NP完全问题(见文献),因此,到目前为止有关交叉数的结果比较少,特别是对于星图Sm与轮Wn的笛卡儿积的交叉数,六阶图与星图Sn的笛卡儿积的交叉数的研究更少.本文首先介绍了交叉数的背景和预备知识,然后在第二章证明了星图S3与轮Wn的笛卡儿积的交叉数为2[(n-1)2/4]+[n/2]+5,n≥3,在第三章证明了轮W4与星图Sn的笛卡儿积的为交叉数为Z(5,n)+2n+[n/2],n≥1,在第四章确定一个六阶图F与星图Sn的笛卡儿积的交叉数为Z(6,n)+2[n/2],n≥1,在第五章确定了两个完全二部图去边后的交叉数即cr(K3,n/e)=Z(3,n)-[n/2]+1,cr(K4,ne)=Z(4,n)-[n/2]+1.最后提出了研究工作在发展中的一些问题以及作者在以后将致力于前进的方向.
其他文献
本课题主要研究具有负顾客到达的两类休假排队系统.一类是具有Bernoulli反馈和负顾客到达的M(M[X])/G/1休假排队系统,另一类是有负顾客到达的M/G/1休假可修排队系统.对于具有B
本文旨在基于中国入世及金融市场全面对外开放的背景下,将有限理性动态古诺模型引入商业银行市场中,将混沌理论引入到此模型中,建立了非线性成本函数下的银行竞争模型,一个竞争策
本文研究广义区间变时滞系统的鲁棒H弹性控制问题,给出了具有离散和分布变时滞的广义区间系统的鲁棒H弹性控制判据。全文包括以下三章。 第一章介绍了时滞系统的研究背景及
本文在设计控制器时引入基于T-S模糊模型的神经网络自适应控制器,使得系统在故障情况下能够在线对消不确定项和模糊建模误差的影响,保证系统具有期望的鲁棒跟踪性能,克服了单
本文基于Type-2模糊T-S模型设计模糊控制器,使得控制系统能够在被控对象复杂、测量数据少的情况下,解决由不确定因素引起的不同类型的复杂故障,以保证设备在外界干扰强的情况下
本文的主要目的是研究单纯李代数的子代数的形心。着重讨论了这些李代数的极大幂零子代数和Borel子代数形心的结构,证明了所有单李代数极大幂零子代数的形心的维数比该李代数
本文主要研究了带色散项Degasperis-Procesi方程、带色散项周期Degasperis-Procesi方程的爆破理论及双Sine-Gordon方程精确解的性质,这些方程都具有奇异波。 D-P方程(Degas