论文部分内容阅读
自Euler发表第一篇图论论文以来,图的理论逐渐建立并完善和丰富起来。在图论中,图的控制理论占据着举足轻重的地位:一方面对于许多实际问题,可以用图进行建模,将其转化为计算图的控制数问题来解决;另一方面,图的控制理论不仅对图的其它理论的研究有着重要的影响,同时也深深地影响着其他学科的发展,如运筹学、网络理论、博弈论、化学、生物学、物理学、社会科学、语言学等。在图的控制理论中,确定图的控制数是一个最基本的问题,Garey和Johnson在[1]中已经证明:确定任意图的控制数问题是一个NP-完全问题。于是,确定控制数的尽可能好的上界和下界就具有非常重要的意义。而控制数通常是由控制函数决定的,因此要想获得控制数,首先要选择合适的控制函数。 本文主要讨论了图的减边控制函数,对比研究了图的减边全控制函数和反减边全控制函数,最后讨论了图的全反符号控制函数和全减边控制函数。 本文主要做了以下工作: 在第一章的绪论部分,我们对图论尤其是图的控制理论问题的背景知识、应用范围和主要研究方向进行简要回顾,然后对本文所涉及的一些图的定义、符号及图之间的运算关系进行介绍,最后对本文的后续章节的主要结构安排进行了简要介绍。 在第二章,我们讨论了图的减边控制数的一些新的界限,减边控制数的定义是由徐保根教授在2007年引入的,在其论文中留下了一些问题,我们对其中的一个问题进行了初步研究,得到了一般图的新的减边控制数的界限。 在第三章,我们在给出图的减边全控制数和反减边全控制数定义的基础上,对比研究了一般图的关于这两类边控制函数的界限,给出了用图的顶点数、边数以及最大度和最小度来表示的一般图的两类边控制数的界限,最后给出路、圈和轮图的减边全控制数和反减边全控制数。 在第四章,我们研究了一般图的全反符号控制数的上界,并且对于特殊图——圈。 在第五章,我们提出了全减控制函数的定义,该定义是对全控制函数和全符号控制函数的一种自然推广,从而使控制更具有普遍意义。在此基础上,我们得到了一般图关于全减控制函数的界限。 在第六章,我们对前面得到的结果进行总结和回顾,同时对本文将来的研究方向进行了展望,以期对将来的研究起到一定的作用。