广义Petersen图P(n,2)和循环图C(n;{1,4})的支配数

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:xiaolan
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图的支配问题是近年来图论中一个比较活跃的研究领域。图的支配数问题是其中一类重要问题,它在网络设计中有许多实际应用。比如在一个通讯网络的一些节点上放置发射器,要求每个发射器的节点一定和某个发射器的节点有一个直接的通讯线路。如何选择节点,使得放置的发射器的数目最小,这就是一个支配数问题。计算图的支配数问题属于NP-完全问题,因此至今只有少数图的支配数被找到并证明。 本文利用计算图的支配数算法计算出n比较小的时候广义Petersen图P(n,2)和循环图C(n;{1,4})的支配数,并构造出n比较小的时候这两类图的支配集,从中找出规律,推出任意n情况下的支配集,从而确定出广义Petersen图P(n,2)和循环图C(n;{1,4})的支配数上界。同时通过计算机计算得的结果,本文给出了广义Petersen图P(n,2)和循环图C(n;{1,4})的支配数的定理。
其他文献
随着Internet中Web服务的数目和种类的增加,如何在诸多服务中找到符合要求的服务,即服务匹配,成为利用Web服务进行资源共享必须解决的问题。当前Web服务并没有以语义网为基础
本体作为语义网的基石,在语义网中起着越来越重要的作用,在经常变化的环境中,本体很难一成不变。为了有效的研究本体进化,本文从用户操作出发。首先设计了用于形式化用户操作的用
粗糙集理论不依赖于所需处理的数据集合之外的任何先验信息,它对不精确、不确定、不完整的信息和知识具有很强的分析处理能力。20世纪50年代末以来,关于粗糙集理论和应用的研
视频、图像和音频等多媒体数据已经成为信息处理领域的主要信息媒体,其中音频占有很重要地地位。传统的基于文本的检索存在主观性和不完整性等缺点,为此基于内容的音频检索成为
数字技术的飞速发展以及互联网的普及给人们的工作和生活带来了巨大便利。但是,正如我们所看到的,利用网络的开放性和共享性所进行的一些恶意的行为,诸如侵犯版权、信息篡改
计算机技术与图像处理技术的进步,使得流场测试领域迅速发展与提高。PIV(Particle Image Velocimetry)技术是近二十多年发展起来的非接触流场测量技术,是一种非常有发展前景的
进入新世纪以来,网络基础设施架构和网络应用都得到了迅猛的发展,计算机网络普及程度和网络用户数量的急剧增长,随之带来的网络安全问题也与日俱增。在众多的安全威胁中,间谍
近年来,在企业级应用开发环境中,面向对象的开发方式已经成为主流,而关系数据库是目前使用最广泛的数据库,因此,在开发过程中大都会采用面向对象的应用与关系数据库相结合的
三维地震数据体中蕴涵着地下岩层的丰富信息,以前由于没有合适的三维显示技术,人们只好利用一条条地震剖面和水平切片来显示三维地震数据。这样导致了大量信息的丢失,多年以前人
中国是自然灾害频繁发生的国家,也是世界上灾害最严重、受灾历史最早、成灾种类最多的少数国家之一。每年由于自然灾害造成严重的人员伤亡和五六百亿元的直接经济损失。针对自