几类图的控制参数的理论与算法

来源 :上海大学 | 被引量 : 3次 | 上传用户:skjthit
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近三十多年来,随着计算机科学和网络通讯技术的飞速发展,图论研究也呈现出异常活跃的趋势,而控制数理论也许是其中发展最快的领域.图的控制数理论作为图论的一个重要研究方向,在相关学科领域,例如计算机科学、通讯网络、编码理论、运筹学以及社会学等领域具有广泛的应用.目前,关于图的控制数理论研究主要集中在四个方面:(1)各类控制参数的界的确定,相互之间关系的研究,以及控制参数与图的其他参数,如色数的关系研究;(2)各类控制参数计算复杂性的研究及其算法的设计;(3)函数控制数及其相关课题的研究;(4)控制数理论在相关学科中的应用研究. 本文所做的工作主要包括以下五部分:第一,我们确定了一般连通图及无爪立方图上电力控制数的准确上界,并对达到其上界的极值图进行了刻画(有关结果已被《DiscreteMathematics》录用);并分别讨论了外平面图及一般平面图上电力控制数的界(有关结果已被《JournalofShanghaiUniversity》录用). 第二,我们研究了两类新的控制函数:负边控制函数和负星控制函数;确定了负边控制数的界,并对达到其上界的阶数为偶数的极值图进行了刻画;并且讨论了这两类控制参数与其他控制参数的关系(有关结果已被《ArsCombinatoria》录用). 第三,我们对达到图的2-距离控制数已知上界的极值图进行了完全刻画.第四,我们给出了二部置换图上无圈控制集的线性时间算法,并研究了三种情况下直线簇上区间图的最小连通控制集算法(有关结果已发表在《上海大学学报(自然科学版)》). 第五,我们构造了具有最小可能边数且最小度为k的任意大的无限唯一k-可着色图类(有关结果已被《JournalofShanghaiUniversity》录用).
其他文献
近年来,随着生物识别技术的兴起,虹膜识别技术被日益关注。由于虹膜识别技术对个体识别具有高度的可靠性,已成为目前生物识别中最有发展前景的识别技术之一。与其它生物识别技术
电力工业放松管制,引入竞争的市场机制,逐步建立电力市场来优化资源配置是整个电力系统的发展趋势。电力市场中电价的确定是最本质、最关键的部分,如何合理的根据市场需求确定相
1965年,L.A.Zadeh教授提出模糊集的概念,标志着模糊数学这门学科的诞生,也为模糊逻辑的产生奠定了基础.1973年,Zadeh教授又首先将模糊数学的思想和方法应用于模糊推理,提出了著名
学位