路径与完全图,完全二分图的交图的交叉数

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:goeas
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
1983年,Garey与Johnson证明:确定一个任意图的交叉数问题是Np-困难的(NP-complete).计算一个给定图的交叉数也是非常困难的,目前,只有很少图族的交叉数是已知的.完全图,完全二分图,广义Petersen图,交图,循环图等图族的交叉数等则是近年来交叉数领域研究的主要问题. 在交图的交叉数方向目前只给出了路径,圈以及星图与一些顶点数较少的图的交图的交叉数. 本文对路径与完全图的交图Km×Pn以及路径与完全二分图的交图Km,n×P1的交叉数进行研究.在这一研究方向,1994年Klesc给出cr(K4×Pn)=2n,2001年Klesc又给出了cr(K2,3×Pn)=2n,cr(K5×Pn)=6n.本文在此基础上,分别给出了路径与完全图的交图,路径与完全二分图的交图的交叉数上界:cr(Km×Pn)≤1/4[m+1/2][m-1/2][m-2/2](n[m+4/2]+[m-4/2]),m≥3,n≥1,cr(Km,n×P1)≤(l-1)([n+2/2][n+1/2][m/2][m-1/2]+m[n/2][n-1/2])+2([n+1/2][n/2][m/2][m-1/2]+[m/2][n/2][n-1/2],m≥2,n≥2,l≥1,及路径与完全图的交图的交叉数下界公式:cr(Km×Pn)≥(n-1)cr(Km+2-e)+2cr(Km+1),m≥3,n≥1,并且进一步确定了路径与完全图的交图,路径与完全二分图的交图中的一部分图,即当m=6时,K6×Pn以及m=2时,K2,n×P1的交叉数:cr(K6×Pn)=15n+3,n≥1,cr(K2,n×P1)=2l[n/2][n-1/2],n≥1,l≥1. 目前,已经确定了的交图的交叉数均为顶点数较少的图的交叉数,对于本文所研究的两类图,由于目前已知的顶点数较小时的交叉数均与本文所给的上界相符,本文猜想所给出的上界就是交叉数的值.
其他文献
随着互联网进入了“Web2.0”时代,用户已经不再只是信息浏览者,同时也是信息的制造者。网络信息产生总量的呈指数级上升的趋势,传统的搜索引擎技术逐渐难以对用户的检索请求
车辆导航系统是智能交通系统的重要组成部分,它除了能够显示电子地图和确定自身位置外,还能够进行信息查询和规划达到目的地的最优路线,并能引导车辆驾驶者到达目的地,从而提高道
近年来,随着互联网的迅速发展,网络安全问题得到了社会的广泛关注。网络攻击形式日趋复杂,入侵检测系统作为传统网络防火墙的补充,在网络安全方面不断发挥越来越重要的作用。
可伸缩视频编码对于可变带宽下的多媒体传输、不同存储容量的媒体存储和不同显示能力的终端都具有重要的意义。可伸缩编码只需一次性编码就能满足不同带宽、不同分辨率和帧率
随着Internet 的发展和经济全球一体化进程的加速,企业不仅要关注自身的运作,而且更要关注与其他企业之间的协同和合作。在这种新的形式下,企业之间的电子商务和协同商务的规模
本文针对面向系统的有效安全评估方法欠缺的现状,提出了一个新颖的基于UML的安全评估方法。它是一种既符合国际安全标准,又偏重于技术分析的,专注于信息系统的快速评估方法。
随着宽带网络设施的日益完善,许多高带宽的多播应用层出不穷。传统的防火墙由于缺乏对多播数据转发的支持,成为了多播应用中的阻碍。因此迫切需要一种能够按需转发多播数据流、
随着我国经济的发展,私家车的市场越来越大,汽车上的娱乐设施——汽车音响有着广阔的市场前景。此外,汽车导航是近年来兴起的一种汽车驾驶辅助设备,正逐渐走入千家万户。它能够根
面对诸多挑战与威胁,具有积极防御功能的入侵检测系统,已经成为网络安全防护体系中的重要组成部分。然而,计算机技术和网络技术的飞速发展,给传统的入侵检测系统带来了前所未有的
肖像画是一种非常流行的艺术表现形式。肖像画,特别是人脸的肖像可以艺术化地表现出个人的面部特性。但是,绘制肖像画,特别是要想把人物的脸部特征用线条简洁的肖像画描绘出来,并