论文部分内容阅读
在近四十年来，随着计算机科学和网络通讯技术的迅速发展，图论也得到了飞速发展，而控制数理论的研究是图论中发展最快的几个领域之一.控制数理论能够快速发展的主要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社会网络等理论与实践中有着重要的作用.
对任意图，人们发现几乎所有的控制参数的判定问题均是NP-完全的，所以对它们的上、下界进行精确估计以及极值图的刻画成为十分有趣的问题.由于概率方法在图参数的界的估计方面具有独特的作用，因此借助概率方法研究控制数的界一直受到关注.本文主要用概率方法研究了几类控制数的界.
本文的主要内容和结果分为以下三部分：
第一部分，首次利用组合差异分析理论中的部分着色方法得到任意图上的符号全控制数的概率结果(有关结果被《Ars Cornbinatoria》录用).
第二部分，利用经典的概率方法得到限制控制数的一个全新的上界.
第三部分，首先得到了路和圈上负边全控制数的精确值，然后得到了任意图的负边全控制数的上界，最后给出了负边全控制数关于边数m，最大度△和最小度δ的下界.