关于图的控制函数-运筹学与控制论专业论文.docxVIP

独创性声明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表和撰写的研究成果，也不包含为获得华 东交通大学或其他教育机构的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 本人签名_ 日期 关于论文使用授权的说明 本人完全了解华东交通大学有关保留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅。学校可以公布论 文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 必威体育官网网址的论文在解密后遵守此规定，本论文无必威体育官网网址内容。 本人签名_ 导师签名 日期 摘要 摘要 I I 关于图的控制函数 摘要 自 Euler 发表第一篇图论论文以来，图的理论逐渐建立并完善和丰富起来。在图论 中，图的控制理论占据着举足轻重的地位：一方面对于许多实际问题，可以用图进行建 模，将其转化为计算图的控制数问题来解决；另一方面，图的控制理论不仅对图的其它 理论的研究有着重要的影响，同时也深深地影响着其他学科的发展，如运筹学、网络理 论、博弈论、化学、生物学、物理学、社会科学、语言学等。在图的控制理论中，确定 图的控制数是一个最基本的问题，Garey 和 Johnson 在[1]中已经证明：确定任意图的控 制数问题是一个 NP-完全问题。于是，确定控制数的尽可能好的上界和下界就具有非常 重要的意义。而控制数通常是由控制函数决定的，因此要想获得控制数，首先要选择合 适的控制函数。 本文主要讨论了图的减边控制函数，对比研究了图的减边全控制函数和反减边全控 制函数，最后讨论了图的全反符号控制函数和全减边控制函数。 本文主要做了以下工作： 在第一章的绪论部分，我们对图论尤其是图的控制理论问题的背景知识、应用范围 和主要研究方向进行简要回顾，然后对本文所涉及的一些图的定义、符号及图之间的运 算关系进行介绍，最后对本文的后续章节的主要结构安排进行了简要介绍。 在第二章，我们讨论了图的减边控制数的一些新的界限，减边控制数的定义是由徐 保根教授在 2007 年引入的，在其论文中留下了一些问题，我们对其中的一个问题进行 了初步研究，得到了一般图的新的减边控制数的界限。 在第三章，我们在给出图的减边全控制数和反减边全控制数定义的基础上，对比研 究了一般图的关于这两类边控制函数的界限，给出了用图的顶点数、边数以及最大度和 最小度来表示的一般图的两类边控制数的界限，最后给出路、圈和轮图的减边全控制数 和反减边全控制数。 在第四章，我们研究了一般图的全反符号控制数的上界，并且对于特殊图——圈 C (n ??3) ，有 ? (C ) ???? n trs n ??  2n ? 5 ???e  。对任一路 Pn (n ??3) ，有 ????2n ?  1,当n  0或3或4(mod 5)时， ?? ? ? ( ? (P ) ? trs n ? 5 ???? ? 。 ???2n ?, 当n 1或2(mod 5)时. ? ???? 5 ?? ? II II 在第五章，我们提出了全减控制函数的定义，该定义是对全控制函数和全符号控制 函数的一种自然推广，从而使控制更具有普遍意义。在此基础上，我们得到了一般图关 于全减控制函数的界限。 在第六章，我们对前面得到的结果进行总结和回顾，同时对本文将来的研究方向进 行了展望，以期对将来的研究起到一定的作用。 关键词：减边全控制函数，反减边全控制函数，全反符号控制函数，全减控制函数 Abs Abstract PAGE PAGE VI ON DOMINATING FUNCTIONS OF GRAPHS ABSTRACT Since Euler published the first paper on graph theory, the graph theory has been gradually established and completed and has gained abundant achievements. In graph theory, the domination theory of graphs holds an important position: on one hand, for many practical problems, we can build models using graph theory to convert them to calculate the domination numbers of graphs to solve；On the other