W<,3,n>的支配问题与二部图的弧的公有性研究

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:toon126
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论是研究由线连接的点集的理论。图论是组合数学的一个重要分支,同时也是离散数学的一个重要组成部分。随着计算机科学与数学的发展,图论已经成为人们研究自然科学以及社会科学的一个重要工具。 图的支配问题是近年来图论中一个比较活跃的研究领域。图的支配问题的研究不仅具有很重要的理论意义,在优化理论、通讯网络的设计与分析、社会科学、计算复杂性和算法设计等许多领域也有很重要的应用背景。 图的支配数问题在网络设计中有许多应用。比如在一个通讯网络的一些节点上放置发射器,要求每个发射器的节点一定和某个发射器的节点有一个直接的通讯线路。如何选择节点,使得放置的发射器的数目最小,这就是一个支配数问题。 计算图的支配数问题属于NP-完全问题,因此至今只有少数图的支配数被找到并证明。本文对Kn(o)del图W3,n的支配数γ(W3,n)及其密切相关的PaCking数ρ(W3,n)进行了较深入的研究。证明了每个圈连通的有向完全二部图有一条公有弧并提出两个问题:(1)假设C是一个圈连通的有向完全二部图G中的一个最大圈,C中所有的弧都是公有弧吗?(2)假设D是一个圈连通的简单有向二部图,D中是否存在一条公有弧? 本文对这两个问题进行了研究,证明了:(1)存在圈连通的有向完全二部图,它的最大圈中至少有一条弧不是公有弧。(2)存在圈连通的简单有向二部图,它的最大圈中所有弧都是公有弧。(3)存在圈连通的简单有向二部图,它的最大圈中至少有一条弧不是公有弧。
其他文献
利用激光扫描获取到的深度数据进行场景的三维重建在数字考古、数字娱乐等许多领域都具有广阔的应用前景。近年来随着激光扫描仪成本的降低和激光扫描技术的发展,基于激光扫描
本文从CSCD技术的网络化需求入手,分析Web Services概念体系在协同设计中的作用,将Web Services和CSCD技术应用于变压器结构设计,提出了一种基于Web Services的CSCD在变压器设计中的应用体系结构。在分析协同设计系统架构的基础上,对协同设计的关键技术,如协同感知方法、冲突消解算法等进行了研究,建立了协同设计中支持产品的全域信息模型;同时,对协同设计进行了过程建模。
P2P电子商务在现实生活中发挥了越来越重要的作用。基于P2P的电子商务较之C/S体系下的电子商务,在灵活性、可扩展性、系统健壮性及投入成本等方面都具很强的竞争优势。但在方
图书馆是人们获取知识和信息的主要来源,图书馆的主要宗旨就是全心全意为读者服务。随着信息技术和网络技术的飞速发展,给图书馆的服务带来了新的挑战。为了提高服务质量和工作
本文分析了B/S架构MIS系统的安全需求,研究了MIS页面文件和数据库系统的保护技术。使用信息摘要、数字签名等方法和外挂轮询技术对传统页面保护策略进行了改进,提高了对MIS页
泛化的EBMT(Example-based machine translation)是针对传统EBMT的一种改进方案,它利用翻译模板取代翻译实例,这样既减小了实例库的规模,同时也在一定程度上提高了模板匹配的
随着互联网的发展,网络应用成为了计算机系统应用的研究热点。同时,以P2P为代表的网络结构将网络应用推向新的高潮。本文的主要目的是研究并开发了一套基于结构化P2P网络的多
网基础理论的研究和发展如今已相当的成熟。目前,网在实际应用领域的研究已成为网研究的侧重点了。但传统网理论由于无法处理非确定信息,从而造成网在建模、处理和分析不确定
大规模的双语命名实体库可以有效的改进机器翻译、跨语言检索等系统的性能。因而前人提出了很多抓取双语命名实体的方法。早期的方法主要是从平行语料中进行抽取,这类方法存
随着传统应用系统集成技术弊端的不断暴露,企业迫切需要一套更经济、更有效的将各种应用系统集成起来的方法。本文主要针对传统技术的种种不足,利用Web Services的高松散藕合