论文部分内容阅读
随着计算机科学的迅速发展,图论随之也得到了飞速发展,而近几十年来图的控制数理论成为图论中发展最快的领域之一。控制数理论能够快速发展的主要原因是它在组合优化、编码理论、计算机科学、通信网络、监视系统和社会网络等理论与实践中有着重要的应用背景。图的函数(全)控制数是经典(全)控制数概念的一类自然推广。由于函数的引入,致使利用函数性质来研究(全)控制数成为可能。目前,函数控制数已成为图的控制集理论中一个崭新而富有挑战性的研究方向。
人们已发现,对任意图已定义的几类函数控制数的判定问题均是NP-完全的,所以对它们的上、下界进行估计以及对其极值图结构的刻画成为十分有意义的问题。本文研究了几类函数全控制数,其主要结果分为以下两部分:
第一部分(第三章),首先建立了任意图的符号边全控制数(γst(G))的几个下界,接着得到了完全图和完全偶图的符号边全控制数(γst(G)),这些结果是全新的;(有关结果被《International Journal of Pure and Applied Mathematics》录用)第二部分(第四章),建立了一些笛卡尔积图的符号全控制数(γst(G))的几个下界,接着得到了一类特殊有向图的符号全控制数的精确值,这些结果也是最新的。