【摘 要】
:
M.R.GareyandD.S.Johnson已经证明确定图的交叉数是一个NP完全问题(见文献[1],因为其难度,我们能够确定交叉数的图类非常少,在许多情况下,即使找出图的交叉数的一个好的上界
论文部分内容阅读
M.R.GareyandD.S.Johnson已经证明确定图的交叉数是一个NP完全问题(见文献[1],因为其难度,我们能够确定交叉数的图类非常少,在许多情况下,即使找出图的交叉数的一个好的上界或下界也是非常困难.目前,很多文献都是在研究一些特殊图类的交叉数,例如:完全图、完全二部图、完全三部图、循环图及一些特殊图类的笛卡尔积图等.本文研究路与某些图类的笛卡尔积图的交叉数.第一章:交代了本文的写作背景,交叉数研究在国内外发展动态,研究工作的意义以及本文中要解决的问题和创新之处.第二章:基本概念和性质介绍了阅读本文所需要的预备知识其中主要包括交叉数的概念,并介绍了在后面文章中会出现的一些相关概念,性质以及常用到的一些定理.第三章:我们寻求了一种好画法,从而给出了路Pm与轮Wn的笛卡尔积交叉数的一个上界即cr(Pm×Wn){=0,n≤2,
=(m-1)[(n-1)/4]+(m+1),n=3,4,
≤(m-1)[(n-1)2]+(m+1),n≥5.并且证明了当m=1,2,3时的交叉数与此上界是符合的.这里,Pn表示边长为n的路,Wn表示由一点到一个n圈Cn的悬挂,也即从独点K1向Cn的所有n个点分别连一条边所得图.第四章:我们确定了5个六阶图与路Pn的笛卡尔积图的交叉数.除了每个定理都寻求到一个好画法外,定理1,2的完成是通过交叉数的一个重要性质得到,定理3,4,5的证明是各自独立完成,整个证明思路看似相同,但实际上在各种细节问题上各有独特之处.第五章:提出了研究工作在发展中的几个问题以及作者在以后将致力于前进的方向.
其他文献
密码加密方案主要分为两类:分组密码和流密码.像DES或AES的分组密码是多轮加密的叠加.而每轮加密都涉及从二元向量空间Vn到向量空间Vm的向量输出布尔函数,这样的布尔函数也称为
根据各种学科发展和应用的需要,Orlicz空间有各种不同形式的推广,Musielak-Orlicz空间是较为常见的一种。一致凸性质、β性质和弱β性质都是Banach空间的重要几何概念,它在逼近
轩岗煤电公司刘家梁矿自2002年重组改制以来,矿党委积极探索党建工作的新载体,实施了“四大工程”,收到了明显效果。一是以“党员形象语言”活动为重点的窗口工程。“党员形
投射模和内射模是环模理论中最重要的模类,它们也构成了同调代数的主要研究对象。它们性质的研究有着非常重要的意义和广泛的应用。本论文研究了模的投射性质,并利用Grothe
第一章 对捕食者具有脉冲作用的Lotka-Volterra捕食-食饵系统的灭绝和持久性 在种群生态学中,Lotka-Volterra模型是一个基本的模型,模型按其生态意义可分为三类:捕食与食
随着移动端技术的日益发展,手机与网络的结合推动了手机媒体的快速发展,其强大的功能受到了大学生群体的青睐,成为了大学生活的重要组成部分之一,对高校大学生管理工作提出了
本论文分别讨论了几类时滞偏差分方程解的振动性和两类时滞偏差分方程的正解不存在性,同时对非齐次线性偏差分方程的稳定性进行了研究。 对于常系数时滞偏差分方程,讨论
支撑向量机是建立在统计学习理论基础上的模式识别方法,是近年来机器学习的研究热点,随着其在理论和算法上的不断完善,现已成为机器学习的有力工具。在机器学习中,总假设每个
在全党弘扬求真务实精神,大兴求真务实之风,是以胡锦涛为总书记的党中央以战略的思维、深邃的眼光和科学的态度提出的一个十分重要而又具有根本意义的大问题。当前,一项重要
我们知道,在抽样调查中并不总能获得感兴趣特征y的精确值,测量误差常常存在。而坚持对大量样本单位获得精确测量值将耗资巨大。因此,常代之以两个或多个在精度和费用上明显不同