图的控制数理论中的概率方法

来源 :上海大学 | 被引量 : 0次 | 上传用户:mengminyan
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在近四十年来,随着计算机科学和网络通讯技术的迅速发展,图论也得到了飞速发展,而控制数理论的研究是图论中发展最快的几个领域之一.控制数理论能够快速发展的主要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社会网络等理论与实践中有着重要的作用. 对任意图,人们发现几乎所有的控制参数的判定问题均是NP-完全的,所以对它们的上、下界进行精确估计以及极值图的刻画成为十分有趣的问题.由于概率方法在图参数的界的估计方面具有独特的作用,因此借助概率方法研究控制数的界一直受到关注.本文主要用概率方法研究了几类控制数的界. 本文的主要内容和结果分为以下三部分: 第一部分,首次利用组合差异分析理论中的部分着色方法得到任意图上的符号全控制数的概率结果(有关结果被《Ars Cornbinatoria》录用). 第二部分,利用经典的概率方法得到限制控制数的一个全新的上界. 第三部分,首先得到了路和圈上负边全控制数的精确值,然后得到了任意图的负边全控制数的上界,最后给出了负边全控制数关于边数m,最大度△和最小度δ的下界.
其他文献
本文主要研究具有Calderon-Zygmund核的Toeplitz型算子在带非双倍测度的Lebesgues空间和Morrery空间,以及带Lebesgue测度的变指数Lebesgue空间上的有界性.附带地也给出了一类多
本文主要对一种真正的无网格法——径向基函数配点法进行了研究,并将此方法应用于求解对流扩散方程,重点求解了非线性对流扩散方程.本文共分四章.第一章概述了径向基函数配点法
对于时滞微分方程,由于其应用背景的广泛性,引起了很多的专家学者的注意,并取得了很多很好的研究成果,但他们对方程的研究主要还是集中在系统解的存在性,唯-性,有界性与稳定性这些
近年来,对于在国民经济发展中起着骨干性、支撑性作用的房地产业而言,房地产税改革被赋予了新的内涵,并再次引起了各界的广泛关注。然而,我国现行的房地产税制仍执行早前颁布