W<,3,n>和K<,m>□C<,n>的交叉数

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:pootcat
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的交叉数是衡量图的非平面性的一个重要参数,Garey和Johnson证明了计算图的交叉数问题是NP完全的。目前仅确定了少数几类图的交叉数。完全图,完全二分图,广义Petersen图,循环图,顶点数较小的图与路径、圈或者星图的交图是交叉数问题中活跃的研究对象。 Kn(?)del图是一种互连网络,研究互连网络的交叉数有助于更好地理解其拓扑性质。本文研究了Kn(?)del图W3,n(n≥8,n为偶数)的交叉数。首先利用计算机构造了W3,n交叉数较少的画法,给出交叉数上界;然后设计了W3,n的边分组方式和交叉点计数函数给出其下界。最终证明: cr(W3,8)=0;cr(W3,10)=1;cr(W3,n)=[n/6]+n mod 6/2,当n≥12时。 Ringeisen和Beineke给出了K3□Cn以及K4□Cn的交叉数。本文进一步研究了完全图和圈的交图Km□Cn的交叉数。通过设计Km□Cn的分组方式和交叉点计数方法,给出了Km□Cn交叉数的下界: cr(Km□Cn)≥n cr(Km+2)。通过改进计算图的交叉数算法CCN的限界条件,利用计算机构造了Km□Cn好的画法,给出了Km□Cn交叉数的上界: cr(Km□Cn)≤n/4[m+2/2][m+1/2][2/2][m-1/2](n为偶数); cr(Km□Cn)≤n/4[m+2/2][m+1/2][m/2][m-1/2]+[m-1/2]2(n为奇数)。因为m≤12时Guy给出的完全图交叉数猜想成立,所以当m≤10,n为偶数时,有: cr(Km□Cn)=n/4[m+2/2][m+1/2][m/2][m-1/2](m≤10且n为偶数)。当n为奇数时,利用计算机构造出了K5□Cn,K6□Cn和K7口Cn的交叉数更少的画法,进一步改进了上界。从而完全确定了这三类图的交叉数: cr(K5□Cn)=9n;cr(K6□Cn)=18n;cr(K7□Cn)=36n。
其他文献
P2P(Peer-to-Peer)是一种分布式计算模式,通过节点之间的直接交换实现资源和服务的共享。P2P网络分为非结构化P2P网络、结构化P2P网络和松散结构化P2P网络。由于非结构化P2P网
工作流技术是计算机支持协同工作研究领域中出现的一项新技术,它是实现企业业务过程建模,过程管理最终实现业务过程自动化的核心技术。工作流技术的研究对企业的业务流程重组
本文研究数据交换的问题,其目的是为实现各“信息孤岛”之间互联互通,信息共享。在数据交换中关键的两点是各数据源之间的数据异构问题及交换过程的动态配置问题。针对上述两个
随着GIS的普及和计算机网络技术的发展,诞生了WebGIS技术并得到了较快的发展。但是,由于现有的GIS系统相对封闭,很难实现真正意义上的空间信息共享,阻碍了GIS社会化、大众化
随着电信行业的市场竞争不断加剧,特别是在2008年,国家对电信运营商再度整合重组,电信市场形成了一种相对均衡的电信、移动、联通三方旗鼓相当的全业务运营竞争格局。中国电信的
随着互联网规模的不断发展,人们对网络服务质量(QoS)的需求越来越高,当今高速网络中的多媒体应用不但对网络有很高的带宽要求,而且要求信息传输的低延迟和低抖动等,需要提供端到
无线传感器网络能实时监测、感知、采集和处理各种监测对象的信息,在军事、环境监测和工业生产等方面具有十分广阔的应用前景,是当前国际上备受关注的新兴前沿研究热点之一。
作为石油技术开放标准协会(POSC)所采用的一项行业标准,国际上,CGM图形格式文件是石油勘探软件的最重要的输出形式,在国际化与本地化几近成为同一个概念的今天,作为一个国际
网格监控系统通过实时获取、保存资源和平台的信息,为网格的正常运行和管理控制提供支持。目前的网格监控系统在信息处理问题上存在聚合信息不全面,聚合方式简单,监控数据的
随着计算机应用技术的快速发展,应用系统的复杂程度越来越高,相应的开发出高质量的软件也就越来越困难。从一个好的观点或需求出发,到最终变成一个要实际运行的软件产品,其间